A Fast Randomized Algorithm for the Approximation of Matrices
Abstract
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 log"l"; the resulting procedure can construct a rank-k approximation Z from the entries of A at a cost proportional to mn log"k"+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 +1"st 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 31, 2007
- Accession Number
- ADA471819
Entities
People
- Edo Liberty
- Franco Woolfe
- Mark Tygert
- Vladimir Rokhlin, Jr.
Organizations
- Yale University