Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions Export

@article{citeulike:5841463, 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 recent research which demonstrates that \emph{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. In particular, these techniques offer a route toward principal component analysis (PCA) for petascale data. 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, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.}, archivePrefix = {arXiv}, author = {Halko, Nathan and Martinsson, Per-Gunnar and Tropp, Joel A.}, citeulike-article-id = {5841463}, citeulike-linkout-0 = {http://arxiv.org/abs/0909.4061}, citeulike-linkout-1 = {http://arxiv.org/pdf/0909.4061}, eprint = {0909.4061}, keywords = {cluster-computing, linear-algebra, randomized-algorithm}, month = {Sep}, posted-at = {2009-11-07 20:18:02}, priority = {2}, title = {Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions}, url = {http://arxiv.org/abs/0909.4061}, year = {2009} }

TY - JOUR ID - citeulike:5841463 L3 - citeulike-article-id:5841463 N2 - 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 recent research which demonstrates that \emph{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. In particular, these techniques offer a route toward principal component analysis (PCA) for petascale data. 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, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis. TI - Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions KW - cluster-computing KW - linear-algebra KW - randomized-algorithm AU - Halko, Nathan AU - Martinsson, Per-Gunnar AU - Tropp, Joel PY - 2009/Sep/22/ UR - http://arxiv.org/abs/0909.4061 ER -