A Randomized Algorithm for the Approximation of Matrices
Abstract
Given an m n matrix A and a positive integer k, we introduce a randomized procedure for the approximation of A with a matrix B of rank k. The procedure relies on applying A(T) to a collection of l random vectors, where l is an integer equal to or slightly greater than k; the scheme is efficient whenever A and A(T) can be applied rapidly to arbitrary vectors. The discrepancy ||B - A|| is of the same order as the (k + 1)st greatest singular value sigma k+1 of A, with negligible probability of even moderately large deviations. The actual estimates derived in the paper are fairly complicated, but simplify when l - k is fixed at a small nonnegative integer. For example, according to one of our estimates for l - k = 20, the probability that kB Ak is greater than 10 k(k + 20)m n sigma k+1 is less than 10(- 17). The paper contains a number of estimates for ||B - A||, including several that are stronger (but more detailed) than the preceding example. The scheme provides a simple, efficient means for constructing an accurate approximation to the Singular Value Decomposition of A, and operates reliably independently of the structure of the matrix A. The results are illustrated via several numerical examples.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 07, 2006
- Accession Number
- ADA458927
Entities
People
- Mark Tygert
- Per-gunnar Martinsson
- Vladimir Rokhlin, Jr.
Organizations
- Yale University