1. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.
- Author
-
Halko, N., Martinsson, P. G., and Tropp, J. A.
- Subjects
- *
ALGORITHMS , *EIGENVALUES , *MATHEMATICAL decomposition , *APPROXIMATION algorithms , *SINGULAR value decomposition , *PRINCIPAL components analysis - Abstract
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 scientific computing. This work surveys and extends recent research which demonstrates that randomization offers 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 specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m x n matrix, (i) For a dense input matrix, randomized algorithms require O(mn log (k)) floating-point operations (flops) in contrast to O(mnk) for classical algorithms, (ii) For a sparse input matrix, the flop 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 fit 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. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF