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 Z of rank k. The procedure relies on applying A(exp 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 A(exp T) can be applied rapidly to arbitrary vectors. The discrepancy between A and Z is of the same order as the (k+1)(exp 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 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 root(k + 20)msigmak+1 is less than 10(exp -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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 29, 2006
- Accession Number
- ADA458932
Entities
People
- Mark Tygert
- Per-gunnar Martinsson
- Vladimir Rockhlin
Organizations
- Yale University