A fast algorithm for approximating the singular value decomposition of a matrix
Mark Tygert, Applied Mathematics,Yale University


This talk will describe a randomized algorithm for the low-rank approximation of arbitrary matrices. Constructing a low-rank approximation is the core step in computing several of the greatest singular values and corresponding singular vectors of a matrix. The new randomized procedure is generally significantly faster than the classical pivoted "QR" decomposition algorithms (such as Gram-Schmidt or Householder), yet ensures similar or better accuracy.

In order to compute a nearly optimally accurate rank-k approximation to an n x n matrix, the new algorithm typically requires O(n**2 log(k) + n k**2) floating-point operations, whereas pivoted "QR" decomposition algorithms require at least kn**2 flops. Moreover, the algorithm runs faster than the
classical algorithms in empirical tests on any of several standard PC microprocessor cores (for almost any k). Furthermore, the scheme parallelizes naturally. The results will be illustrated via numerical examples and applications.

This is joint work with Edo Liberty, Vladimir Rokhlin, and Franco Woolfe.