Wednesday, July 27, 2011

Finding Structure with Randomness

The other day, Cable and I were looking for the PCA of a very large matrix. We compared the randomized approach to a direct one... it was not even funny. After four hours on one of the latest Mac, the direct SVD was still clogging all the processes while I was done in less than 20 seconds on a small PC. Today, the question is, when are we going to have a Random-LAPACK ?

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientiﬁc computing. This work surveys and extends recent research which demonstrates that randomization oﬀers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed—either explicitly or implicitly—to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and/or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The speciﬁc beneﬁts of randomized techniques depend on the computational environment. Consider the model problem of ﬁnding the k dominant components of the singular value decomposition of an m × n matrix. (i) For a dense input matrix, randomized algorithms require O(mn log(k)) ﬂoating-point operations (ﬂops) in contrast to O(mnk) for classical algorithms. (ii) For a sparse input matrix, the ﬂop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures. (iii) For a matrix that is too large to ﬁt in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.

For reminder:

Petar Maymounkov said...

Is this what you are looking for:

http://pdos.csail.mit.edu/~petar/papers/blendenpik-v1.pdf

This is random preconditioning, which works well in practice.

Igor said...

Yes.