The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Randomized algorithms for the low-rank approximation of matrices
Open accessAbstract
We describe two recently proposed randomized algorithms for the construction of low-rank approximations to matrices, and demonstrate their application ( inter alia ) to the evaluation of the singular value decompositions of numerically low-rank matrices. Being probabilistic, the schemes described here have a finite probability of failure; in most cases, this probability is rather negligible (10 −17 is a typical value). In many situations, the new procedures are considerably more efficient and reliable than the classical (deterministic) ones; they also parallelize naturally. We present several numerical examples to illustrate the performance of the schemes.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The text we found for this paper looks like another document, so the self-check wasn’t run.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Björck, Å., Dahlquist, G. G., & Anderson, N. (1974) · Cited by 1,719
Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
Gu, M., & Eisenstat, S. C. (1996) · SIAM Journal on Scientific Computing · doi:10.1137/0917055 · Cited by 677
On the Compression of Low Rank Matrices
Cheng, H., Gimbutas, Z., Martinsson, P. G., & Rokhlin, V. (2005) · SIAM Journal on Scientific Computing · doi:10.1137/030602678 · Cited by 301
Self-citationA fast randomized algorithm for the approximation of matrices
Woolfe, F., Liberty, E., Rokhlin, V., & Tygert, M. (2008) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.12.002 · Cited by 280
Self-citationA Randomized Algorithm for the Approximation of Matrices
Martinsson, P.-G., Rockhlin, V., & Tygert, M. (2006) · doi:10.21236/ada458932 · Cited by 268
Self-citationEstimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
Kuczyński, J., & Woźniakowski, H. (1992) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0613066 · Cited by 251
Incomplete Cross Approximation in the Mosaic-Skeleton Method
Tyrtyshnikov, E. (2000) · Computing · doi:10.1007/s006070070031 · Cited by 249
Efficient computation of the DFT with only a subset of input or output points
Sorensen, H. V., & Burrus, C. S. (1993) · IEEE Transactions on Signal Processing · doi:10.1109/78.205723 · Cited by 245
Estimating Extremal Eigenvalues and Condition Numbers of Matrices
Dixon, J. D. (1983) · SIAM Journal on Numerical Analysis · doi:10.1137/0720053 · Cited by 106
Research works printed but not linked: 1
- N Ailon B Chazelle (ACM Press New York) pp. 557–563 (2006).
Cited by
Items 501–541 of 541
(2018) · Society of Exploration Geophysicists eBooks · doi:10.1190/1.9781560803447.refs
(2019) · Cambridge University Press eBooks · doi:10.1017/9781108380690.015
Brunton, S. L., & Kutz, J. N. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108380690.001 · Cited by 1
Brunton, S. L., & Kutz, J. N. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108380690.014
Brunton, S. L., & Kutz, J. N. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108380690.016
Wamalwa, R. N., & Mukanzi, C. (2022) · The International Journal of Humanities & Social Studies · doi:10.24940/theijhss/2022/v10/i3/hs2203-017
Subspaces Analysis for Random Projection UTV Framework
Yuan, J. L. (2022) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/21m1451592
A compact Heart iteration for low-rank approximations of large matrices
Dax, A. (2023) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2023.115467
Yan, J., Zhang, Y., Liu, S., Luo, J., Pu, W., & Yang, J. (2023) · IEEE International Geoscience and Remote Sensing Symposium (IGARSS) · doi:10.1109/igarss52108.2023.10282573
Descomposición en valores singulares y análisis de factores en ciencias humanas y sociales
Pernice, S. A. (2024) · Revista de Métodos Cuantitativos para la Economía y la Empresa · doi:10.46661/rev.metodoscuant.econ.empresa.8004
Butterfly Factorization with Error Guarantees
Le, Q.-T., Zheng, L., Riccietti, E., & Gribonval, R. (2025) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/24m1708796 · Cited by 8
Physical Layer Security of AF-Based Hybrid Satellite-Terrestrial Networks
Park, H., Kim, M., & Choi, J. J. (2024) · International Conference on Information and Communication Technology Convergence (ICTC) · doi:10.1109/ictc62082.2024.10827605
On the Fast Direct Solution of Low-Frequency Integral Formulations via Operator Filtering
Merlini, A., Henry, C., Consoli, D., Dély, A., Rahmouni, L., & Andriulli, F. P. (2023) · URSI International Symposium on Electromagnetic Theory · doi:10.1109/emts57498.2023.10925280
Structure-Aware Analyses and Algorithms for Interpolative Decompositions
Armstrong, R., Buzali, A., & Damle, A. (2025) · SIAM Journal on Scientific Computing · doi:10.1137/23m1610811
Wang, D., Hu, Y., Fang, Y., & Liu, Q. H. (2025) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2025.3569704
Kielstra, P. M., Shi, T., Luo, H., Qian, J., & Liu, Y. (2025) · Multiscale Modeling and Simulation · doi:10.1137/24m1707821
Hidayatullah, M. N., & Azis, A. M. (2025) · International Journal of Scientific Research and Management (IJSRM) · doi:10.18535/ijsrm/v13i06.m01
A Restarted and Randomized Algorithm for Evaluating Energy of Extremely Large-Scale Graph
Wu, G., Li, K., & Wang, J. (2025) · Journal of Computational Mathematics · doi:10.4208/jcm.2506-m2024-0192
Hidayatullah, M. N., & Aziz, A. M. (2025) · Jurnal Manajemen Indonesia · doi:10.25124/jmi.v25i2.9075
Alaviani, S. S., Katuri, J., Ali, J., & Anubi, O. M. (2025) · Journal of Micro-Bio Robotics · doi:10.1007/s12213-025-00197-0
Learning with Multiple Similarities
Kumar, A. (2013) · University Libraries (University of Maryland)
Mixed-precision Interpolative Decomposition on GPUs
Ma, Q., & Imamura, T. (2026) · International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia) · doi:10.1145/3773656.3773681
Liu, J., Li, Z., & Song, J. (2026) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2025.3650282
Efficient genome-wide association studies via low-rank approximations
Chen, Z., Liang, H. Y., & Wei, P. (2026) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2026.108343
Resolvent analysis of shock-laden flows
Murthy, S. R., & Bodony, D. J. (2026) · Journal of Fluid Mechanics · doi:10.1017/jfm.2026.11255
MSSA based seismic interpolation using non-convex regularization
Zhu, Y., Cao, J., & Zhao, J. (2026) · Journal of Geophysics and Engineering · doi:10.1093/jge/gxag043
Gumerov, K., Rigg, S., & Slevinsky, R. M. (2026) · SIAM Journal on Scientific Computing · doi:10.1137/25m1724213
Algorithmic and theoretical aspects of sparse deep neural networks
Le, Q.-T. (2023) · theses.fr (ABES) · doi:10.70675/01b91cd8zefbaz442az9887zbfcec3e1132f · Cited by 1
Liu, Q., & 陈, 凌. (2026) · SCIENTIA SINICA Terrae · doi:10.1360/n072025-0415
Linearized versus nonlinear estimates of uncertainty in full waveform inversion
Zhao, X., & Curtis, A. (2026) · Geophysical Journal International · doi:10.1093/gji/ggag248
STTID: High-Performance Sparse Tensor-Train Interpolative Decomposition
Meng, Z., Stoudenmire, M., Pierce, K., Mueller, F., & Li, J. (2026) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps65963.2026.00015
Improving Sketching Algorithms for Low-Rank Matrix Approximation via Sketch-Power Iterations
Chang, C., & Yang, Y. (2026) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/25m1760143
TZ: Achieving High-Ratio Scientific Data Compression on GPUs with Global Data Decomposition
Yang, Z., Li, R., Subrahmanya, A. N., Rao, V., Di, S., Underwood, R., Zhang, L., Liu, J., Cappello, F., & Zhao, K. (2026) · ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC) · doi:10.1145/3806645.3807811
Wu, D., Gao, C., & Wu, Q. (2026) · IEEE Antennas and Wireless Propagation Letters · doi:10.1109/lawp.2026.3724999
Noor, A., & Yan, S. (2026) · Digest - IEEE Antennas and Propagation Society. International Symposium · doi:10.1109/ap-s/usnc-ursi60190.2026.11675728
Advanced Supervised Principal Component Analysis for Regression Task
Krammer, P. H., Kenyeres, M., & Hluchý, L. (2026) · Lecture notes in networks and systems · doi:10.1007/978-3-032-38803-2_28
Chen, C., Wang, L.-T., Liu, X., Shen, L., Li, H., & Peng, B. (2026) · Remote Sensing · doi:10.3390/rs18203478
Noor, A., & Yan, S. (2026) · International Conference on Electromagnetics in Advanced Applications (ICEAA) · doi:10.23919/iceaa69870.2026.11725036
Metadata
- Authors
- Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M.
- Affiliations
- Yale University (US)
- University of Colorado Boulder (US)
- Department of Computer Science and
- Venue
- Proceedings of the National Academy of Sciences
- Publisher
- National Academy of Sciences
- Published
- 2007-12-18
- Volume
- 104
- Issue
- 51
- Pages
- 20167-20172
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- PMC
- PMC2154402
- OpenAlex
- W1968691112
- Cited by
- 559
- References
- 14
- Citations by year
- 2026: 25 · 2025: 22 · 2024: 21 · 2023: 29 · 2022: 26 · 2021: 35 · 2020: 44 · 2019: 56 · 2018: 37 · 2017: 41 · 2016: 44 · 2015: 41 · 2014: 33 · 2013: 27 · 2012: 27
- FWCI
- 8.96
- Type
- journal article
- Language
- en
- Open access
- green
- www.ncbi.nlm.nih.gov
- Locations
- Proceedings of the National Academy of Sciences (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- ePubWU Institutional Repository (Wirtschaftsuniversität Wien) (submittedVersion)
- WU Research (submittedVersion, other-oa)
- Funders
- Japan Society for the Promotion of Science (26820298, 25000003, 16H00923)
- National Institute of Environmental Health Sciences (27302C0031)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Applied Mathematics › Statistical and numerical algorithms
- Keywords
- low-rank approximation, randomized algorithms, singular value decomposition, parallel algorithms, matrix approximation
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.