A randomized algorithm for the decomposition of matrices

Given an m x 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 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 between A and Z is of the same order as root lm times 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 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 parallel to A - Z parallel to is greater than 10 root(k + 20)m sigma(k+1) is less than 10(-17). The paper contains a number of estimates for parallel to A - Z parallel to, 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 A(T) 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. (C) 2010 Elsevier Inc. All rights reserved.