Matrix Sketching - Best Algorithms in Time and Space       

Mathematics Accomplishment | 2009 - 2013

IBM researchers: Kenneth L. Clarkson and David P. Woodruff

Where the work was doneIBM Almaden Research Center

What we accomplished: Using statistically bounded approximation and sampling techniques, developed several matrix operations with smallest space and time requirements for several common algorithms such as matrix products, linear regression, low-rank approximation, and approximation of matrix rank.

Related linksLow Rank Approximation and Regression in Input Sparsity Time (ACM Symposium on the Theory of Computing, STOC'2013): "Using our sparse embedding matrices, we obtain the fastest known algorithms for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and lp-regression."

Numerical Linear Algebra in the Streaming Model (STOC'2009): "Many algorithms for numerical linear algebra have been proposed, with substantial gains in performance over older algorithms, at the cost of producing results satisfying Monte Carlo performance guarantees: with high probability, the error is small. These algorithms pick random samples of the rows, columns, or individual entries of the matrices, or else compute a small number of random linear combinations of the rows or columns of the matrices. These compressed versions of the matrices are then used for further computation. The two general approaches are sampling or sketching, respectively.  Algorithms of this kind are generally also pass-efficient, requiring only a constant number of passes over the matrix data for creating samples or sketches, and other work."