The DOI matches its Crossref record; 206 of the 206 references it cites were found in a registry or an index.
Randomized numerical linear algebra: Foundations and algorithms
Abstract
This survey describes probabilistic algorithms for linear algebraic computations, such as factorizing matrices and solving linear systems. It focuses on techniques that have a proven track record for real-world problems. The paper treats both the theoretical foundations of the subject and practical computational issues. Topics include norm estimation, matrix approximation by sampling, structured and unstructured random embeddings, linear regression problems, low-rank approximation, subspace iteration and Krylov methods, error estimation and adaptivity, interpolatory and CUR factorizations, Nyström approximation of positive semidefinite matrices, single-view (‘streaming’) algorithms, full rank-revealing factorizations, solvers for linear systems, and approximation of kernel matrices that arise in machine learning and in scientific computing.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
Advances in Neural Information Processing Systems 29
Teymur, O., Zygalakis, K., & Calderhead, B. (2016) · Cited by 13,887
Advances in Neural Information Processing Systems 25
Zhang, Y., Sutton, C. A., Storkey, A., & Zoubin Ghahramani, A. (2012) · Cited by 12,653
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,703
Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference
(2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.001.0001 · Cited by 8,890
Methods of conjugate gradients for solving linear systems
Hestenes, M. R., & Stiefel, E. (1952) · Journal of Research of the National Bureau of Standards · doi:10.6028/jres.049.044 · Cited by 8,132
The Jackknife, the Bootstrap and Other Resampling Plans
Efron, B. (1982) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970319 · Cited by 8,120
Large-Scale Machine Learning with Stochastic Gradient Descent
Bottou, L. (2010) · Proceedings of COMPSTAT'2010 · doi:10.1007/978-3-7908-2604-3_16 · Cited by 5,795
A fast algorithm for particle simulations
Greengard, L., & Rokhlin, V (1987) · Journal of Computational Physics · doi:10.1016/0021-9991(87)90140-9 · Cited by 4,868
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Self-citationA hierarchical O(N log N) force-calculation algorithm
Barnes, J., & Hut, P. (1986) · Nature · doi:10.1038/324446a0 · Cited by 3,698
Trefethen, L. N., & Bau, III (1997) · doi:10.1137/1.9780898719574 · Cited by 3,301
Aspects of Multivariate Statistical Theory
Gleser, L. J. (1984) · Technometrics · doi:10.1080/00401706.1984.10487948 · Cited by 3,277
(1999) · Cited by 3,186
Aspects of multivariate statistical theory
Muirhead, R. J. 1. (1982) · Cited by 3,032
Bhatia, R. (1996) · Cited by 2,847
Advances in Neural Information Processing Systems 20
Bonilla, E. V., Chai, K. M. A., & Williams, C. K. I. (2008) · neural information processing systems · Cited by 2,846
Random Features for Large-Scale Kernel Machines
Rahimi, A., & Recht, B. (2007) · Cited by 2,783
(2008) · Choice Reviews Online · doi:10.5860/choice.45-5628 · Cited by 2,725
The Jackknife: The Bootstrap and Other Resampling Plans.
Low, L. Y., & Efron, B. (1983) · Journal of the American Statistical Association · doi:10.2307/2288218 · Cited by 2,702
A Mathematical Introduction to Compressive Sensing
Foucart, S., & Rauhut, H. (2013) · Applied and Numerical Harmonic Analysis · doi:10.1007/978-0-8176-4948-7 · Cited by 2,548
Probability and Random Processes
(2004) · Elsevier eBooks · doi:10.1016/b978-0-12-172651-5.x5000-3 · Cited by 2,535
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Bhatia, R. (1997) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-0653-8 · Cited by 2,336
Simplified neuron model as a principal component analyzer
Oja, E. (1982) · Journal of Mathematical Biology · doi:10.1007/bf00275687 · Cited by 2,309
Aspects of Multivariate Statistical Theory
Muirhead, R. J. (1982) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316559 · Cited by 2,260
On the distribution of the largest eigenvalue in principal components analysis
Johnstone, I. M. (2001) · The Annals of Statistics · doi:10.1214/aos/1009210544 · Cited by 1,949
Probability and Random Processes.
Grimmett, G. R., & Stirzaker, D. R. (2001) · doi:10.1093/oso/9780198572237.001.0001 · Cited by 1,850
Concentration Inequalities: A Nonasymptotic Theory of Independence
Boucheron, S., Lugosi, G., & Massart, P. (2013) · doi:10.1093/acprof:oso/9780199535255.001.0001 · Cited by 1,768
Using the Nyström Method to Speed Up Kernel Machines
Williams, C. K. I., & Seeger, M. (2000) · Cited by 1,646
The Schur Complement and Its Applications
(2005) · Numerical Methods and Algorithms · doi:10.1007/b105056 · Cited by 1,615
Spectral Analysis of Large Dimensional Random Matrices
Bai, Z., & Silverstein, J. W. (2010) · Springer Series in Statistics · doi:10.1007/978-1-4419-0661-8 · Cited by 1,544
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,527
Optimal state-determination by mutually unbiased measurements
Wootters, W. K., & Fields, B. D. (1989) · Annals of Physics · doi:10.1016/0003-4916(89)90322-9 · Cited by 1,424
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
High-Dimensional Probability: An Introduction with Applications in Data Science
Vershynin, R. (2018) · Cambridge University Press eBooks · doi:10.1017/9781108231596 · Cited by 1,382
Eigenvalues and Condition Numbers of Random Matrices
Edelman, A. (1988) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0609045 · Cited by 1,284
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
A Sparse Matrix Arithmetic Based on $\Cal H$ -Matrices. Part I: Introduction to ${\Cal H}$ -Matrices
Hackbusch, W. (1999) · Computing · doi:10.1007/s006070050015 · Cited by 1,179
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning
Petros Drineas, B., & Mahoney, M. W. (2005) · Journal of Machine Learning Research · doi:10.5555/1046920.1194916 · Cited by 1,174
Ledoux, M., & Talagrand, M. (1991) · doi:10.1007/978-3-642-20212-4 · Cited by 1,160
The Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
High-Dimensional Probability: An Introduction with Applications in Data Science
Vershynin, R. (2018) · Cited by 1,031
1 USER-FRIENDLY TAIL BOUNDS FOR SUMS OF RANDOM MATRICES
Tropp, J. A. (2010) · Cited by 1,018
Self-citationThe geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (1995) · Combinatorica · doi:10.1007/bf01200757 · Cited by 952
The Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2010) · Cited by 921
A Randomized Kaczmarz Algorithm with Exponential Convergence
Strohmer, T., & Vershynin, R. (2009) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9030-4 · Cited by 903
The Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2012) · Foundations of Computational Mathematics · doi:10.1007/s10208-012-9135-7 · Cited by 886
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
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
Automatically Tuned Linear Algebra Software
Whaley, R. C., & Dongarra, J. J. (1998) · Conference on High Performance Computing (Supercomputing) · doi:10.5555/509058.509096 · Cited by 854
On sparse reconstruction from Fourier and Gaussian measurements
Rudelson, M., & Vershynin, R. (2008) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20227 · Cited by 847
An Introduction to Matrix Concentration Inequalities
Tropp, J. A. (2015) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000048 · Cited by 792
Self-citationCUR matrix decompositions for improved data analysis
Mahoney, M. W., & Drineas, P. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0803205106 · Cited by 773
Lectures on Applied Mathematics
(2000) · Springer eBooks · doi:10.1007/978-3-642-59709-1 · Cited by 767
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
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-citationEfficient 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
Fast Direct Methods for Gaussian Processes
Ambikasaran, S., Foreman-Mackey, D., Greengard, L., Hogg, D. W., & O'Neil, M. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2448083 · Cited by 669
Improved Approximation Algorithms for Large Matrices via Random Projections
Sarlos, T. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.37 · Cited by 646
A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
Hutchinson, M. F. (1990) · Communications in Statistics - Simulation and Computation · doi:10.1080/03610919008812866 · Cited by 610
Normal Approximation by Stein’s Method
Chen, L. H. Y., Goldstein, L., & Shao, Q.-M. (2011) · Probability and Its Applications · doi:10.1007/978-3-642-15007-4 · Cited by 591
Efficient svm training using low-rank kernel representations
Fine, S., & Scheinberg, K. (2002) · doi:10.5555/944790.944812 · Cited by 579
Positive definite functions on spheres
Schoenberg, I. J. (1942) · Duke Mathematical Journal · doi:10.1215/s0012-7094-42-00908-6 · Cited by 568
Randomized algorithms for the low-rank approximation of matrices
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709640104 · Cited by 559
Self-citationWeighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning
Rahimi, A., & Recht, B. (2008) · Cited by 558
Latent Semantic Indexing: A Probabilistic Analysis
Papadimitriou, C. H., Raghavan, P., Tamaki, H., & Vempala, S. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1711 · Cited by 556
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442696 · Cited by 552
Fast monte-carlo algorithms for finding low-rank approximations
Frieze, A., Kannan, R., & Vempala, S. (2004) · Journal of the ACM · doi:10.1145/1039488.1039494 · Cited by 500
Graph Sparsification by Effective Resistances
Spielman, D. A., & Srivastava, N. (2011) · SIAM Journal on Computing · doi:10.1137/080734029 · Cited by 489
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Bach, F., & Moulines, É. (2011) · Cited by 488
Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442684 · Cited by 487
The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
Ailon, N., & Chazelle, B. (2009) · SIAM Journal on Computing · doi:10.1137/060673096 · Cited by 479
Relative-Error $CUR$ Matrix Decompositions
Drineas, P., Mahoney, M. W., & Muthukrishnan, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/07070471x · Cited by 461
Local Operator Theory, Random Matrices and Banach Spaces
(2001) · Handbook of the Geometry of Banach Spaces · doi:10.1016/s1874-5849(01)80010-3 · Cited by 432
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Needell, D., Srebro, N., & Ward, R. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0864-7 · Cited by 432
Strong converse for identification via quantum channels
Ahlswede, R., & Winter, A. (2002) · IEEE Transactions on Information Theory · doi:10.1109/18.985947 · Cited by 423
A Randomized Algorithm for Principal Component Analysis
Rokhlin, V., Szlam, A., & Tygert, M. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/080736417 · Cited by 422
Living on the edge: phase transitions in convex programs with random data
Amelunxen, D., Lotz, M., McCoy, M. B., & Tropp, J. A. (2014) · Information and Inference · doi:10.1093/imaiai/iau005 · Cited by 413
Self-citationRandomized 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
Communication-optimal Parallel and Sequential QR and LU Factorizations
Demmel, J., Grigori, L., Hoemmen, M., & Langou, J. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/080731992 · Cited by 407
Construction and Arithmetics of H -Matrices
Grasedyck, L., & Hackbusch, W. (2003) · Computing · doi:10.1007/s00607-003-0019-1 · Cited by 402
Matrices, Moments and Quadrature with Applications
Golub, G., & Meurant, G. (2009) · Princeton University Press eBooks · doi:10.1515/9781400833887 · Cited by 395
Fundamentals of Stein’s method
Ross, N. (2011) · Probability Surveys · doi:10.1214/11-ps182 · Cited by 387
Stewart, G. W. (1998) · Cited by 383
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Ailon, N., & Chazelle, B. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132597 · Cited by 379
Random Vectors in the Isotropic Position
Rudelson, M. (1999) · Journal of Functional Analysis · doi:10.1006/jfan.1998.3384 · Cited by 371
The DFT: An Owner's Manual for the Discrete Fourier Transform
Briggs, W. L., & Henson, V. E. (1995) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971514 · Cited by 366
Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
Leventhal, D., & Lewis, A. S. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0456 · Cited by 349
Paved with good intentions: Analysis of a randomized block Kaczmarz method
Needell, D., & Tropp, J. A. (2013) · Linear Algebra and its Applications · doi:10.1016/j.laa.2012.12.022 · Cited by 323
Self-citationMonotone Funktionen, Stieltjessche Integrale und harmonische Analyse
Bochner, S. (1933) · Mathematische Annalen · doi:10.1007/bf01452844 · Cited by 318
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442702 · Cited by 310
Fast and scalable polynomial kernels via explicit feature maps
Pham, N., & Pagh, R. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487591 · Cited by 306
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-citationNumerical linear algebra in the streaming model
Clarkson, K. L., & Woodruff, D. P. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536445 · Cited by 301
Fast computation of low-rank matrix approximations
Achlioptas, D., & Mcsherry, F. (2007) · Journal of the ACM · doi:10.1145/1219092.1219097 · Cited by 292
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
Freedman's inequality for matrix martingales
Tropp, J. A. (2011) · Electronic Communications in Probability · doi:10.1214/ecp.v16-1624 · Cited by 289
Self-citationAn improved approximation algorithm for the column subset selection problem
Boutsidis, C., Mahoney, M. W., & Petros Drineas, B. (2009) · doi:10.5555/1496770.1496875 · Cited by 286
On Milman's inequality and random subspaces which escape through a mesh in ℝ n
Gordon, Y. (1988) · Lecture Notes in Mathematics · doi:10.1007/bfb0081737 · Cited by 282
Über Die Praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben
Nyström, E. J. (1930) · Acta Mathematica · doi:10.1007/bf02547521 · Cited by 281
A 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
A Randomized Algorithm for the Approximation of Matrices
Martinsson, P.-G., Rockhlin, V., & Tygert, M. (2006) · doi:10.21236/ada458932 · Cited by 268
Self-citationRandom Filters for Compressive Sampling and Reconstruction
Tropp, J. A., Wakin, M. B., Duarte, M. F., Baron, D., & Baraniuk, R. G. (2006) · 2006 IEEE International Conference on Acoustics Speed and Signal Processing Proceedings · doi:10.1109/icassp.2006.1660793 · Cited by 264
Self-citationSampling methods for the Nyström method
Kumar, S., Mohri, M., & Talwalkar, A. (2012) · Cited by 252
Estimating 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
Predictive low-rank decomposition for kernel methods
Bach, F. R., & Jordan, M. I. (2005) · Proceedings of the 22nd international conference on Machine learning - ICML '05 · doi:10.1145/1102351.1102356 · Cited by 238
A survey of direct methods for sparse linear systems
Davis, T. A., Rajamanickam, S., & Sid-Lakhdar, W. M. (2016) · Acta Numerica · doi:10.1017/s0962492916000076 · Cited by 238
The DFT: An Owner's Manual for the Discrete Fourier Transform
Strawderman, R., Briggs, W. L., & Henson, V. E. (1999) · Journal of the American Statistical Association · doi:10.2307/2669724 · Cited by 235
A fast ?Monte-Carlo cross-validation? procedure for large least squares problems with noisy data
Girard, A. (1989) · Numerische Mathematik · doi:10.1007/bf01395775 · Cited by 220
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edgesPreprint
Oliveira, R. I. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0911.0600 · Cited by 216
Subspace Iteration Randomization and Singular Value Problems
Gu, M. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/130938700 · Cited by 209
Randomized Iterative Methods for Linear Systems
Gower, R. M., & Richtárik, P. (2015) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/15m1025487 · Cited by 209
Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
Sankar, A., Spielman, D. A., & Teng, S.-H. (2006) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479803436202 · Cited by 207
Neal, R. M. (1996) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-0745-0_2 · Cited by 204
Goreinov, S. A., Oseledets, I. V., Savostyanov, D. V., Tyrtyshnikov, E. E., & Zamarashkin, N. L. (2010) · Matrix Methods: Theory, Algorithms and Applications · doi:10.1142/9789812836021_0015 · Cited by 199
Kahan, W. (1966) · Canadian Mathematical Bulletin · doi:10.4153/cmb-1966-083-2 · Cited by 198
How to generate random matrices from the classical compact groups
Mezzadri, F. (2007) · Cited by 198
Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature
Ubaru, S., Chen, J., & Saad, Y. (2017) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/16m1104974 · Cited by 190
Koroljuk, V. S., & Borovskich, Y. V. (1994) · Springer eBooks · doi:10.1007/978-94-017-3515-5 · Cited by 189
How to generate random matrices from the classical compact groups
Mezzadri, F. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math-ph/0609050 · Cited by 185
A fast randomized algorithm for overdetermined linear least-squares regression
Rokhlin, V., & Tygert, M. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0804869105 · Cited by 183
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple
Kyng, R., & Sachdeva, S. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.68 · Cited by 178
Fastfood - Computing Hilbert Space Expansions in loglinear time
Le, Q. V., Sarlós, T., & Smola, A. J. (2013) · International Conference on Machine Learning · Cited by 175
Generalization Properties of Learning with Random Features
Rudi, A., & Rosasco, L. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04474 · Cited by 174
Fast computation of low rank matrix approximations
Achlioptas, D., & McSherry, F. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380858 · Cited by 172
Demmel, J., Dumitriu, I., & Holtz, O. (2007) · Numerische Mathematik · doi:10.1007/s00211-007-0114-x · Cited by 169
Randomized sketches of convex programs with sharp guarantees
Pilanci, M., & Wainwright, M. J. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6874967 · Cited by 165
Frequent Directions: Simple and Deterministic Matrix Sketching
Ghashami, M., Liberty, E., Phillips, J. M., & Woodruff, D. P. (2016) · SIAM Journal on Computing · doi:10.1137/15m1009718 · Cited by 164
On the Bootstrap of $U$ and $V$ Statistics
Arcones, M. A., & Gine, E. (1992) · The Annals of Statistics · doi:10.1214/aos/1176348650 · Cited by 159
An Introduction to Finite Tight Frames
Waldron, S. F. D. (2018) · Applied and numerical harmonic analysis · doi:10.1007/978-0-8176-4815-2 · Cited by 154
Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squaresPreprint
Pilancı, M., & Wainwright, M. J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.0347 · Cited by 147
Demmel, J. W., Dumitriu, I., & Holtz, O. (2007) · Cited by 143
Golub, G. H., Luk, F. T., & Overton, M. L. (1981) · ACM Transactions on Mathematical Software · doi:10.1145/355945.355946 · Cited by 139
Universality laws for randomized dimension reduction, with applications
Oymak, S., & Tropp, J. A. (2017) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iax011 · Cited by 138
Self-citationCoherence motivated sampling and convergence analysis of least squares polynomial Chaos regression
Hampton, J., & Doostan, A. (2015) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2015.02.006 · Cited by 134
A Fast Randomized Algorithm for Computing a Hierarchically Semiseparable Representation of a Matrix
Martinsson, P. (2011) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/100786617 · Cited by 134
Self-citationRandomized Block Krylov Methods for Stronger and Faster Approximate Singular Value DecompositionPreprint
Musco, C., & Musco, C. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.05477 · Cited by 134
Matrix concentration inequalities via the method of exchangeable pairs
Mackey, L. W., Jordan, M. I., Chen, R. Y., Farrell, B., & Tropp, J. A. (2014) · The Annals of Probability · doi:10.1214/13-aop892 · Cited by 132
Self-citationA Fast Butterfly Algorithm for the Computation of Fourier Integral Operators
Candès, E. J., Demanet, L., & Ying, L. (2009) · Multiscale Modeling and Simulation · doi:10.1137/080734339 · Cited by 130
Kasiviswanathan, S. P., Rudelson, M., Smith, A., & Ullman, J. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806795 · Cited by 129
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
Petros Drineas, B., Mahoney, M. W., & Muthukrishnan, S. (2006) · Lecture notes in computer science · doi:10.1007/11830924_30 · Cited by 125
Randomized Algorithms for Matrices and Data
Mahoney, M. W. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601985071 · Cited by 121
35th International Conference on Very Large Data Bases VLDB 2009
Krikellas, K., Cintra, M. S., & Viglas, S. D. (2009) · Cited by 117
Randomized QR with Column Pivoting
Duersch, J. A., & Gu, M. (2017) · SIAM Journal on Scientific Computing · doi:10.1137/15m1044680 · Cited by 112
Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
Tropp, J. A., Yurtsever, A., Udell, M. R., & Cevher, V. (2019) · SIAM Journal on Scientific Computing · doi:10.1137/18m1201068 · Cited by 109
Self-citationEstimating Extremal Eigenvalues and Condition Numbers of Matrices
Dixon, J. D. (1983) · SIAM Journal on Numerical Analysis · doi:10.1137/0720053 · Cited by 106
Compressed matrix multiplication
Pagh, R. (2013) · ACM Transactions on Computation Theory · doi:10.1145/2493252.2493254 · Cited by 105
Guo, H., Liu, Y., Hu, J., & Michielssen, E. (2017) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2017.2727511 · Cited by 104
Recursive Sampling for the Nyström MethodPreprint
Musco, C., & Musco, C. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.07583 · Cited by 98
Fast construction of hierarchical matrix representation from matrix–vector multiplication
Lin, L., Lu, J., & Lexing Ying, B. (2011) · Journal of Computational Physics · doi:10.1016/j.jcp.2011.02.033 · Cited by 96
Toward a unified theory of sparse dimensionality reduction in Euclidean space
Bourgain, J., Dirksen, S., & Nelson, J. (2015) · Geometric and Functional Analysis · doi:10.1007/s00039-015-0332-9 · Cited by 90
Communication Avoiding Rank Revealing QR Factorization with Column Pivoting
Demmel, J. W., Grigori, L., Gu, M., & Xiang, H. (2015) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/13092157x · Cited by 90
Randomized methods for matrix computations
Martinsson, P. (2018) · IAS/Park City mathematics series · doi:10.1090/pcms/025/04 · Cited by 87
Self-citationTracking Join and Self-Join Sizes in Limited Storage
Alon, N., Gibbons, P. B., Matias, Y., et al. (2002) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1813 · Cited by 86
Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error BoundsPreprint
Wang, S., Gittens, A., & Mahoney, M. W. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.02803 · Cited by 84
Randomized Sparse Direct Solvers
Xia, J. (2013) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/12087116x · Cited by 81
Compact Random Feature MapsPreprint
Hamid, R., Xiao, Y., Gittens, A., & DeCoste, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.4626 · Cited by 81
Efficient algorithms for cur and interpolative matrix decompositions
Voronin, S., & Martinsson, P. (2016) · Advances in Computational Mathematics · doi:10.1007/s10444-016-9494-8 · Cited by 73
Self-citationLi, Y., Yang, H., Martin, E., Ho, K. L., & Lexing Ying, B. (2015) · Multiscale Modeling and Simulation · doi:10.1137/15m1007173 · Cited by 65
Preconditioned Low-rank Riemannian Optimization for Linear Systems with Tensor Product Structure
Kreßner, D., Steinlechner, M., & Vandereycken, B. (2016) · SIAM Journal on Scientific Computing · doi:10.1137/15m1032909 · Cited by 64
Householder QR Factorization With Randomization for Column Pivoting (HQRRP)
Martinsson, P., Quintana‐Ortí, G., Heavner, N., & Geijn, R. A. (2017) · SIAM Journal on Scientific Computing · doi:10.1137/16m1081270 · Cited by 61
Self-citationRandomized algorithms in numerical linear algebra
Kannan, R., & Vempala, S. (2017) · Acta Numerica · doi:10.1017/s0962492917000058 · Cited by 60
A universal sampling method for reconstructing signals with simple Fourier transforms
Avron, H., Kapralov, M., Musco, C., Musco, C., Velingker, A., & Zandieh, A. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316363 · Cited by 60
Random Rotations: Characters and Random Walks on SO(N)
Rosenthal, J. S. (1994) · The Annals of Probability · doi:10.1214/aop/1176988864 · Cited by 58
Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization
Avron, H., Druinsky, A., & Gupta, A. (2015) · Journal of the ACM · doi:10.1145/2814566 · Cited by 57
Li, H., Linderman, G. C., Szlam, A. D., Stanton, K. P., Kluger, Y., & Tygert, M. (2017) · ACM Transactions on Mathematical Software · doi:10.1145/3004053 · Cited by 56
ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions
March, W. B., Xiao, B., & Biros, G. (2015) · SIAM Journal on Scientific Computing · doi:10.1137/140989546 · Cited by 55
Stability of the Lanczos Method for Matrix Function Approximation
Musco, C., Musco, C., & Sidford, A. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975031.105 · Cited by 55
Spectrum estimation from samples
Kong, W., & Valiant, G. J. (2017) · The Annals of Statistics · doi:10.1214/16-aos1525 · Cited by 54
Encrypting by Random Rotations
Sloane, N. J. A. (2007) · Springer eBooks · doi:10.1007/3-540-39466-4_6 · Cited by 52
Spatial mapping with Gaussian processes and nonstationary Fourier features
Ton, J.-F., Flaxman, S. R., Sejdinović, D., & Bhatt, S. (2018) · Spatial Statistics · doi:10.1016/j.spasta.2018.02.002 · Cited by 52
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
Teng, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13562-0_2 · Cited by 49
Lectures on randomized numerical linear algebra
Drineas, P., & Mahoney, M. W. (2018) · IAS/Park City mathematics series · doi:10.1090/pcms/025/01 · Cited by 47
The Achievable Performance of Convex DemixingPreprint
McCoy, M. B., & Tropp, J. A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.7478 · Cited by 45
Self-citationLearning Fast Algorithms for Linear Transforms Using Butterfly Factorizations
Dao, T., Gu, A., Eichhorn, M., Rudra, A., & Ré, C. (2019) · arXiv · doi:10.48550/arxiv.1903.05895 · Cited by 43
Xiao, J., Gu, M., & Langou, J. (2017) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc.2017.00035 · Cited by 42
Dimensionality Reduction of Massive Sparse Datasets Using CoresetsPreprint
Feldman, D., Volkov, M., & Rus, D. L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.01663 · Cited by 41
The cut-off phenomenon for random reflections
Porod, U. (1996) · The Annals of Probability · doi:10.1214/aop/1042644708 · Cited by 37
randUTV: A Blocked Randomized Algorithm for Computing a Rank-Revealing UTV Factorization
Martinsson, P., Quintana‐Ortí, G., & Heavner, N. (2019) · ACM Transactions on Mathematical Software · doi:10.1145/3242670 · Cited by 37
Self-citationEstimating the algorithmic variance of randomized ensembles via the bootstrap
Lopes, M. E. (2019) · The Annals of Statistics · doi:10.1214/18-aos1707 · Cited by 37
Banks, J., Garza-Vargas, J., Kulkarni, A., & Srivastava, N. (2022) · Foundations of Computational Mathematics · doi:10.1007/s10208-022-09577-5 · Cited by 33
On the convergence to equilibrium of Kac’s random walk on matrices
Oliveira, R. I. (2009) · The Annals of Applied Probability · doi:10.1214/08-aap550 · Cited by 30
Interpolative Butterfly Factorization
Li, Y., & Yang, H. (2017) · SIAM Journal on Scientific Computing · doi:10.1137/16m1074941 · Cited by 27
Geometry-oblivious FMM for compressing dense SPD matrices
Yu, C. D., Levitt, J., Reiz, S., & Biros, G. (2017) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3126908.3126921 · Cited by 27
Improved fixed-rank Nyström approximation via QR decomposition: Practical and theoretical aspects
Pourkamali‐Anaraki, F., & Becker, S. (2019) · Neurocomputing · doi:10.1016/j.neucom.2019.06.070 · Cited by 27
Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra
Lim, L., & Weare, J. (2017) · SIAM Review · doi:10.1137/15m1040827 · Cited by 25
Accelerated dense random projections
Zucker, S. W., & Liberty, E. (2009) · Cited by 24
Martinsson, P. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1505.08115 · Cited by 24
Self-citationPolynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
Baldi, P., & Vershynin, R. (2019) · SIAM Journal on Mathematics of Data Science · doi:10.1137/19m1257792 · Cited by 22
Deterministic CUR for Improved Large-Scale Data Analysis: An Empirical Study
Thurau, C., Kersting, K., & Bauckhage, C. (2012) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972825.59 · Cited by 21
Multidimensional butterfly factorization
Li, Y., Yang, H., & Lexing Ying, B. (2017) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2017.04.002 · Cited by 20
On interpolation and integration in finite-dimensional spaces of bounded functions
Martinsson, P., Rokhlin, V., & Tygert, M. (2006) · Communications in Applied Mathematics and Computational Science · doi:10.2140/camcos.2006.1.133 · Cited by 20
Self-citationMalik, O. A., & Becker, S. (2020) · Linear Algebra and its Applications · doi:10.1016/j.laa.2020.05.004 · Cited by 19
Using Random Butterfly Transformations to Avoid Pivoting in Sparse Direct Methods
Baboulin, M., Li, X. S., & Rouet, F.-H. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-17353-5_12 · Cited by 18
Metadata
- Authors
- Martinsson, P.-G., & Tropp, J. A.
- Venue
- Acta Numerica
- Publisher
- Cambridge University Press (CUP)
- Published
- 2020-05
- Volume
- 29
- Pages
- 403-572
- ISSN
- 0962-4929 (ISSN-L)
- 1474-0508
- OpenAlex
- W3108353645
- Cited by
- 300
- References
- 206
- FWCI
- 10.48
- Type
- journal article
- Language
- en
- Open access
- closed
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.