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 Z of rank k. The procedure relies on applying Aexp T to a collection of l random vectors, where l is an integer equal to or slightly greater than k the scheme is e cient whenever A and Aexp T can be applied rapidly to arbitrary vectors. The discrepancy between A and Z is of the same order as the k1exp st 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 are simpler when l-k is a fixed small nonnegative integer. For example, according to one of our estimates for l-k 20, the probability that the spectral norm A- Z is greater than 10 square rootk 20msigmak1 is less than 10exp -17. The paper contains a number of estimates for A-Z, including several that are stronger but more detailed than the preceding example some of the estimates are e ectively independent of m. Thus, given a matrix A of limited numerical rank, such that both A and AT can be applied rapidly to arbitrary vectors, the scheme provides a simple, efficient means for constructing an accurate approximation to a Singular Value Decomposition of A. Furthermore, the algorithm presented here operates reliably independently of the structure of the matrix A. The results are illustrated via several numerical examples.
- Numerical Mathematics