A Fast Randomized Algorithm for the Approximation of Matrices

• Main Authors: Woolfe, Franco, Liberty, Edo, Rokhlin, Vladimir, Tygert, Mark
• Format: Report
• Language: English
• Subjects: ACCURACY; ALGORITHMS; COSTS; DECOMPOSITION; FLOATING POINT OPERATION; GUARANTEES; MATRICES(MATHEMATICS); NUMBERS; Numerical Mathematics; PROBABILITY; RANDOM VARIABLES

We introduce a randomized procedure that, given an m?n matrix A and a positive integer k, approximates A with a matrix Z of rank k. The algorithm relies on applying a structured l ? m random matrix R to each column of A, where l is an integer near to, but greater than, k. The structure of R allows us to apply it to an arbitrary m?1 vector at a cost proportional to m logl; the resulting procedure can construct a rank-k approximation Z from the entries of A at a cost proportional to mn logk+l2 m+n. We prove several bounds on the accuracy of the algorithm; one such bound guarantees that the spectral norm kA − Zk of the discrepancy between A and Z is of the same order as pmax{m, n} times the k +1st greatest singular value k+1 of A, with small probability of large deviations. In contrast, the classical pivoted ?QR? decomposition algorithms such as Gram- Schmidt or Householder require at least kmn floating-point operations in order to compute a similarly accurate rank-k approximation. In practice, the algorithm of this paper is faster than the classical algorithms, as long as k is neither very small nor very large. Furthermore, the algorithm operates reliably independently of the structure of the matrix A, can access each column of A independently and at most twice, and parallelizes naturally. The results are illustrated via several numerical examples. Sponsored in part by AFOSR grant FA9550-05-C-0064 and NGA grants HM1582-06-1-2039, HM1582-06-1-2037.