A randomized algorithm for the decomposition of matrices

Given an m×n matrix A and a positive integer k, we describe a randomized procedure for the approximation of A with a matrix Z 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 between A and Z is of the same order as times the (k+1)st greatest singular value σ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 is less than 10−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 effectively 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.