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. Our new 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 ln(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.
This is joint work with Edo Liberty, Vladimir Rokhlin, and Franco Woolfe.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.