Speaker: Mart Tygert, Yale Applied Math

Time/Date: 1:30 P.M., Wednesday, August 22nd

Location: room 200 AKW

Title:

A fast algorithm for approximating a singular value decomposition of a
matrix


Abstract:

This talk will describe an efficient 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
procedure is generally significantly faster than the classical pivoted
"QR" decomposition algorithms (such as Gram-Schmidt or Householder),
yet ensures similar or better accuracy with high probability.

In fact, in order to compute a nearly optimally accurate rank-k
approximation to an n x n matrix (given the individual entries of the
matrix), the new algorithm typically requires O(n² ln(k) + n k²)
floating-point operations, whereas "QR" decomposition algorithms
require at least kn² flops. Moreover, the algorithm runs faster than
"QR" decomposition algorithms in empirical tests on several standard PC
microprocessors, even when k is quite small or large. The scheme also
uses less storage when the input matrix is to be preserved, and
parallelizes naturally. The results will be illustrated via numerical
examples.

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