The DOI matches its Crossref record; 107 of the 107 references it cites were found in a registry or an index.
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
Open accessAbstract
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 \times n$ matrix. (i) For a dense input matrix, randomized algorithms require $\bigO(mn \log(k))$ floating-point operations (flops) in contrast to $ \bigO(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 $\bigO(k)$ passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
The Elements of Statistical Learning
Hastie, T., Tibshirani, R., & Friedman, J. (2009) · Springer Series in Statistics · doi:10.1007/978-0-387-84858-7 · Cited by 25,970
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Numerical recipes in C: the art of scientific computing
(1993) · Choice Reviews Online · doi:10.5860/choice.30-5638 · Cited by 17,933
Donoho, D. L. (2004) · Cited by 16,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
Cited by
On hyperparameter optimization of machine learning algorithms: Theory and practice
Yang, L., & Shami, A. (2020) · Neurocomputing · doi:10.1016/j.neucom.2020.07.061 · Cited by 3,232
Machine Learning for Fluid Mechanics
Brunton, S. L., Noack, B. R., & Koumoutsakos, P. (2020) · Annual Review of Fluid Mechanics · doi:10.1146/annurev-fluid-010719-060214 · Cited by 3,063
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Single-Cell Map of Diverse Immune Phenotypes in the Breast Tumor Microenvironment
Azizi, E., Carr, A. J., Plitas, G., Cornish, A. E., Konopacki, C., Prabhakaran, S., Nainys, J., Wu, K., Kiseliovas, V., Setty, M., et al. (2018) · Cell · doi:10.1016/j.cell.2018.05.060 · Cited by 1,976
Modal Analysis of Fluid Flows: An Overview
Taira, K., Brunton, S. L., Dawson, S. T. M., Rowley, C. W., Colonius, T., McKeon, B. J., Schmidt, O. T., Gordeyev, S., Theofilis, V., & Ukeiley, L. S. (2017) · AIAA Journal · doi:10.2514/1.j056060 · Cited by 1,894
Greenacre, M., Groenen, P. J. F., Hastie, T., D’Enza, A. I., Markos, A., & Tuzhilina, E. (2022) · Nature Reviews Methods Primers · doi:10.1038/s43586-022-00184-w · Cited by 1,773
Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control
Brunton, S. L., & Kutz, J. N. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108380690 · Cited by 1,154
Exact matrix completion via convex optimization
Candès, E., & Recht, B. (2012) · Communications of the ACM · doi:10.1145/2184319.2184343 · Cited by 996
Efficient integration of heterogeneous single-cell transcriptomes using Scanorama
Hie, B., Bryson, B., & Berger, B. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0113-3 · Cited by 974
pcadapt : an Rpackage to perform genome scans for selection based on principal component analysis
Luu, K., Bazin, E., & Blum, M. G. B. (2017) · Molecular Ecology Resources · doi:10.1111/1755-0998.12592 · Cited by 971
Computational Advertising: Techniques for Targeting Relevant Ads
Woodruff, D. P. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000060 · Cited by 866
Kambatla, K., Kollias, G., Kumar, V., & Grama, A. (2014) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2014.01.003 · Cited by 819
RASL: Robust Alignment by Sparse and Low-Rank Decomposition for Linearly Correlated Images
Peng, Y., Ganesh, A., Wright, J., Xu, W., & Ma, Y. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.282 · Cited by 817
Simultaneous seismic data denoising and reconstruction via multichannel singular spectrum analysis
Oropeza, V., & Sacchi, M. (2011) · Geophysics · doi:10.1190/1.3552706 · Cited by 788
Tensor decompositions for learning latent variable models
(2012) · arXiv (Cornell University) · doi:10.5555/2627435.2697055 · Cited by 779
User-Friendly Tail Bounds for Sums of Random Matrices
Tropp, J. A. (2012) · Foundations of Computational Mathematics · doi:10.1007/s10208-011-9099-z · Cited by 718
Self-citationTran, N. M., Shekhar, K., Whitney, I. E., Jacobi, A., Benhar, I., Hong, G., Yan, W., Adiconis, X., Arnold, M. E., Lee, J. M., et al. (2019) · Neuron · doi:10.1016/j.neuron.2019.11.006 · Cited by 627
A data-driven approach to cleaning large face datasets
Ng, H.-W., & Winkler, S. (2014) · 2014 IEEE International Conference on Image Processing (ICIP) · doi:10.1109/icip.2014.7025068 · Cited by 643
Dynamic Mode Decomposition and Its Variants
Schmid, P. J. (2022) · Annual Review of Fluid Mechanics · doi:10.1146/annurev-fluid-030121-015835 · Cited by 640
Modal Analysis of Fluid Flows: Applications and Outlook
Taira, K., Hemati, M. S., Brunton, S. L., Sun, Y., Duraisamy, K., Bagheri, S., Dawson, S. T. M., & Yeh, C.-A. (2020) · AIAA Journal · doi:10.2514/1.j058462 · Cited by 634
Machine-learning reprogrammable metasurface imager
Li, L., Ruan, H., Liu, C., Li, Y., Shuang, Y., Alù, A., Qiu, C.-W., & Cui, T. J. (2019) · Nature Communications · doi:10.1038/s41467-019-09103-2 · Cited by 592
A literature survey of low‐rank tensor approximation techniques
Grasedyck, L., Kressner, D., & Tobler, C. (2013) · GAMM-Mitteilungen · doi:10.1002/gamm.201310004 · Cited by 577
Modern Koopman Theory for Dynamical Systems
Brunton, S. L., Budišić, M., Kaiser, E., & Kutz, J. N. (2022) · SIAM Review · doi:10.1137/21m1401243 · Cited by 576
Tensor networks for complex quantum systems
Orús, R. (2019) · Nature Reviews Physics · doi:10.1038/s42254-019-0086-7 · Cited by 569
Wild binary segmentation for multiple change-point detection
Fryzlewicz, P. (2014) · The Annals of Statistics · doi:10.1214/14-aos1245 · Cited by 566
Low-Rank Tensor Constrained Multiview Subspace Clustering
Zhang, C., Fu, H., Liu, S., Liu, G., & Cao, X. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.185 · Cited by 566
Stem-like CD8 T cells mediate response of adoptive cell immunotherapy against human cancer
Krishna, S., Lowery, F. J., Copeland, A. R., Bahadiroglu, E., Mukherjee, R., Jia, L., Anibal, J. T., Sachs, A., Adebola, S. O., Gurusamy, D., et al. (2020) · Science · doi:10.1126/science.abb9847 · Cited by 547
Fast interpolation-based t-SNE for improved visualization of single-cell RNA-seq data
Linderman, G. C., Rachh, M., Hoskins, J. G., Steinerberger, S., & Kluger, Y. (2019) · Nature Methods · doi:10.1038/s41592-018-0308-4 · Cited by 534
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Siegel, E. H., Sands, M. K., Van den Noortgate, W., Condon, P., Chang, Y., Dy, J., Quigley, K. S., & Barrett, L. F. (2018) · Psychological Bulletin · doi:10.1037/bul0000128 · Cited by 515
Active Subspace Methods in Theory and Practice: Applications to Kriging Surfaces
Constantine, P. G., Dow, E., & Wang, Q. (2014) · SIAM Journal on Scientific Computing · doi:10.1137/130916138 · Cited by 506
Zhang, Y., Du, B., Zhang, L., & Wang, S. (2016) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2015.2479299 · Cited by 485
Regenerative lineages and immune-mediated pruning in lung cancer metastasis
Laughney, A. M., Hu, J., Campbell, N. R., Bakhoum, S. F., Setty, M., Lavallée, V.-P., Xie, Y., Masilionis, I., Carr, A. J., Kottapalli, S., et al. (2020) · Nature Medicine · doi:10.1038/s41591-019-0750-6 · Cited by 471
Rank Minimization for Snapshot Compressive Imaging
Liu, Y., Yuan, X., Suo, J., Brady, D. J., & Dai, Q. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2873587 · Cited by 466
Molecular signatures of antitumor neoantigen-reactive T cells from metastatic human cancers
Lowery, F. J., Krishna, S., Yossef, R., Parikh, N. B., Chatani, P. D., Zacharakis, N., Parkhurst, M. R., Levin, N., Sindiri, S., Sachs, A., et al. (2022) · Science · doi:10.1126/science.abl5447 · Cited by 447
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
A Simple Baseline for Bayesian Uncertainty in Deep Learning
Maddox, W., Garipov, T., Izmailov, P., Vetrov, D., & Wilson, A. G. (2019) · arXiv · doi:10.48550/arxiv.1902.02476 · Cited by 429
Randomized Algorithms for Matrices and Data
MAHONEY, M. (2012) · Chapman & Hall/CRC Data Mining and Knowledge Discovery Series · doi:10.1201/b11822-37 · Cited by 409
LFMM 2: Fast and Accurate Inference of Gene-Environment Associations in Genome-Wide Studies
Caye, K., Jumentier, B., Lepeule, J., & François, O. (2019) · Molecular Biology and Evolution · doi:10.1093/molbev/msz008 · Cited by 404
Short-term stock market price trend prediction using a comprehensive deep learning system
Shen, J., & Shafiq, M. O. (2020) · Journal of Big Data · doi:10.1186/s40537-020-00333-6 · Cited by 380
Fast Principal-Component Analysis Reveals Convergent Evolution of ADH1B in Europe and East Asia
Galinsky, K. J., Bhatia, G., Loh, P.-R., Georgiev, S., Mukherjee, S., Patterson, N. J., & Price, A. L. (2016) · The American Journal of Human Genetics · doi:10.1016/j.ajhg.2015.12.022 · Cited by 371
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
SVD Compression for Magnetic Resonance Fingerprinting in the Time Domain
McGivney, D. F., Pierre, E., Ma, D., Jiang, Y., Saybasili, H., Gulani, V., & Griswold, M. A. (2014) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2014.2337321 · Cited by 314
Toward a Quantitative Survey of Dimension Reduction Techniques
Espadoto, M., Martins, R. M., Kerren, A., Hirata, N. S. T., & Telea, A. C. (2021) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2019.2944182 · Cited by 309
Fast Principal Component Analysis of Large-Scale Genome-Wide Data
(2014) · doi:10.1371/journal.pone.0093766 · Cited by 305
Amestoy, P. R., Buttari, A., L'Excellent, J.-Y., & Mary, T. (2019) · ACM Transactions on Mathematical Software · doi:10.1145/3242094 · Cited by 305
Randomized numerical linear algebra: Foundations and algorithms
Martinsson, P.-G., & Tropp, J. A. (2020) · Acta Numerica · doi:10.1017/s0962492920000021 · Cited by 300
Self-citationCevher, V., Becker, S., & Schmidt, M. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2329397 · Cited by 300
An Algorithm for the Principal Component Analysis of Large Data Sets
Halko, N., Martinsson, P.-G., Shkolnisky, Y., & Tygert, M. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/100804139 · Cited by 291
Self-citationNew and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
Krahmer, F., & Ward, R. (2011) · SIAM Journal on Mathematical Analysis · doi:10.1137/100810447 · Cited by 290
Unsupervised machine learning for exploratory data analysis in imaging mass spectrometry
Verbeeck, N., Caprioli, R. M., & Van de Plas, R. (2020) · Mass Spectrometry Reviews · doi:10.1002/mas.21602 · Cited by 281
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Cohen, M. B., Elder, S., Musco, C., Musco, C., & Persu, M. (2015) · Proceedings of the forty-seventh annual ACM symposium on Theory of Computing · doi:10.1145/2746539.2746569 · Cited by 276
Zero-preserving imputation of single-cell RNA-seq data
Linderman, G. C., Zhao, J., Roulis, M., Bielecki, P., Flavell, R. A., Nadler, B., & Kluger, Y. (2022) · Nature Communications · doi:10.1038/s41467-021-27729-z · Cited by 275
Data-Driven Aerospace Engineering: Reframing the Industry with Machine Learning
Brunton, S. L., Nathan Kutz, J., Manohar, K., Aravkin, A. Y., Morgansen, K., Klemisch, J., Goebel, N., Buttrick, J., Poskin, J., Blom-Schieber, A. W., et al. (2021) · AIAA Journal · doi:10.2514/1.j060131 · Cited by 270
Hyperspectral Image Denoising via Noise-Adjusted Iterative Low-Rank Matrix Approximation
He, W., Zhang, H., Zhang, L., & Shen, H. (2015) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2015.2398433 · Cited by 269
Sparse PCA corrects for cell type heterogeneity in epigenome-wide association studies
Rahmani, E., Zaitlen, N., Baran, Y., Eng, C., Hu, D., Galanter, J., Oh, S., Burchard, E. G., Eskin, E., Zou, J., et al. (2016) · Nature Methods · doi:10.1038/nmeth.3809 · Cited by 268
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, B., Magdon‐Ismail, M., Mahoney, M. W., & Woodruff, D. P. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.3843 · Cited by 164
Clustering Approach Based on Mini Batch Kmeans for Intrusion Detection System Over Big Data
Peng, K., Leung, V. C. M., & Huang, Q. (2018) · IEEE Access · doi:10.1109/access.2018.2810267 · Cited by 268
Shallow neural networks for fluid flow reconstruction with limited sensors
Erichson, N. B., Mathelin, L., Yao, Z., Brunton, S. L., Mahoney, M. W., & Kutz, J. N. (2020) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2020.0097 · Cited by 259
Ultrasound Small Vessel Imaging With Block-Wise Adaptive Local Clutter Filtering
Song, P., Manduca, A., Trzasko, J. D., & Chen, S. (2017) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2016.2605819 · Cited by 258
Local diversity and fine-scale organization of receptive fields in mouse visual cortex
Bonin, V., Histed, M. H., Yurgenson, S., & Reid, R. C. (2011) · The Journal of Neuroscience · doi:10.1523/jneurosci.2974-11.2011 · Cited by 247
Who’s Who? Detecting and Resolving Sample Anomalies in Human DNA Sequencing Studies with Peddy
Pedersen, B. S., & Quinlan, A. R. (2017) · The American Journal of Human Genetics · doi:10.1016/j.ajhg.2017.01.017 · Cited by 237
Aftab, M., Chen, C., Chau, C.-K., & Rahwan, T. (2017) · Energy and Buildings · doi:10.1016/j.enbuild.2017.07.077 · Cited by 201
Surface Defect Detection via Entity Sparsity Pursuit With Intrinsic Priors
Wang, J., Li, Q., Gan, J., Yu, H., & Yang, X. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2019.2917522 · Cited by 141
Xu, J., Mao, C., Hou, Y., Luo, Y., Binder, J. L., Zhou, Y., Bekris, L. M., Shin, J., Hu, M., Wang, F., et al. (2022) · Cell Reports · doi:10.1016/j.celrep.2022.111717 · Cited by 115
Protein codes promote selective subcellular compartmentalization
Kilgore, H. R., Chinn, I., Mikhael, P. G., Mitnikov, I., Van Dongen, C., Zylberberg, G., Afeyan, L., Banani, S. F., Wilson-Hawken, S., Lee, T. I., et al. (2025) · Science · doi:10.1126/science.adq2634 · Cited by 99
Sketched SVD: Recovering Spectral Features from Compressive Measurements
Gilbert, A. C., Park, J. Y., & Wakin, M. B. (2012) · arXiv · doi:10.48550/arxiv.1211.0361 · Cited by 57
Subset Selection Algorithms: Randomized vs. Deterministic
Broadbent, M., Brown, M., & Penner, K. (2010) · SIAM Undergraduate Research Online · doi:10.1137/09s010435 · Cited by 32
Phenotype prediction from single-cell RNA-seq data using attention-based neural networks
Mao, Y., Lin, Y.-Y., Wong, N. K. Y., Volik, S., Sar, F., Collins, C., & Ester, M. (2024) · Bioinformatics · doi:10.1093/bioinformatics/btae067 · Cited by 31
“Considering the high dimensionality of scRNA-seq data which is likely to result in serious over-fitting, we map the original input to a low dimensional latent space and keep only 50 principal components by principal components analysis (PCA) (Halko et al. 2011).”
MethodSpacecraft Pose Estimation using Principal Component Analysis and a Monocular Camera
Shi, J.-F., Ulrich, S., & Ruel, S. (2017) · AIAA Guidance, Navigation, and Control Conference · doi:10.2514/6.2017-1034 · Cited by 25
Fast approximate computations with Cauchy matrices and polynomials
Pan, V. (2017) · Mathematics of Computation · doi:10.1090/mcom/3204 · Cited by 21
“For efficient alternative techniques, some of which use randomization or heuristics; see [GOS08], [GT01], [HMT11], [LWMRT], [M11], [M11a], [PQY15], [T00], [W14], [XXG12], and the references therein.”
MethodChen, J., Han, X., Liu, Z., Zhou, C., Hu, R., Tabassam, S., Wyatt-Johnson, S. K., Oblak, A. L., Brutkiewicz, R. R., Lin, M., et al. (2026) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2025.3614233 · Cited by 2
“To address the challenge of slowing-decay singular values, both the randomized power iteration algorithm [54] and GoDec [40] operated on ˜ X = ( XX T ) γ X instead of the original input dense data matrix, X .”
Metadata
- Authors
- Halko, N., Martinsson, P. G., & Tropp, J. A.
- Venue
- SIAM Review
- Published
- 2011-01
- Volume
- 53
- Issue
- 2
- Pages
- 217-288
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2117756735
- Cited by
- 4,002
- References
- 107
- FWCI
- 128.87
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.