A Randomized Algorithm for the Approximation of Matrices
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 AT 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 AT can be applied rapidly to arbitrary vectors. The discrepancy B - A is of the same order as the k 1st greatest singular value sigma k1 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 kk 20m n sigma k1 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.
- Numerical Mathematics