Randomized numerical linear algebra: Foundations and algorithms

Melgaard, C. and Gu, M. (2015), Gaussian elimination with randomized complete pivoting. arXiv:1511.08528

Martinsson, P.-G. , Rokhlin, V. and Tygert, M. (2006 a), A randomized algorithm for the approximation of matrices. Yale CS research report YALEU/DCS/RR-1361, Computer Science Department, Yale University.

Vershynin, R. (2019), Concentration inequalities for random tensors. arXiv:1905.00802

Ballard, G. , Demmel, J. , Dumitriu, I. and Rusciano, A. (2019), A generalized randomized rank-revealing factorization. arXiv:1909.06524

10.1080/03610919008812866

10.1137/S0097539704442696

Stewart, 2001, Eigensystems, 2

10.1073/pnas.0709640104

10.1007/978-3-319-40519-3_8

10.1007/BF02358985

Tomczak-Jaegermann, 1974, ‘The moduli of smoothness and convexity and the Rademacher averages of trace classes ${S}_p\left(1\le p<\infty \right)$, Studia Math., 50, 163

O’Neil, M. (2007), A new class of analysis-based fast transforms. PhD thesis, Mathematics, Yale University.

10.1007/s00440-011-0360-9

10.1214/13-AOP892

10.1142/S1793536911000787

10.1109/TIT.2015.2450722

10.1137/07070471X

10.1007/978-3-7908-2604-3_16

10.1007/978-3-642-20212-4

10.1090/conm/026/737400

Sun, Y. , Guo, Y. , Tropp, J. A. and Udell, M. (2018), Tensor random projection for low memory dimension reduction. In 32nd Conference on Neural Information Processing Systems, Montréal, Canada .

10.1214/18-AAP1391

Li, 2014, 2014 ACM Symposium on Theory of Computing (STOC ’14), 174

Kasiviswanathan, 2010, 2010 ACM International Symposium on Theory of Computing (STOC ’10), 775

10.1145/2591796.2591833

Arcones, 1992, ‘On the bootstrap of $u$ and $v$ statistics, Ann. Statist., 20, 655, 10.1214/aos/1176348650

10.1214/ECP.v16-1624

10.1007/BFb0081737

10.1137/1.9780898719574

10.1007/978-1-4612-0653-8

Musco, 2018, 29th Annual ACM–SIAM Symposium on Discrete Algorithms, 1605

Rahimi, 2009, Advances in Neural Information Processing Systems 21, 1313

10.1007/s00607-003-0019-1

Pilanci, 2016, ‘Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares, J. Mach. Learn. Res., 17, 38

10.1109/ICDM.2018.00193

10.1515/9781400833887

10.1109/TAP.2017.2727511

Banks, J. , Vargas, J. G. , Kulkarni, A. and Srivastava, N. (2019), Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time. arXiv:1912.08805

Stewart, 1999, ‘The QLP approximation to the singular value decomposition, SIAM J. Sci. Comput., 20, 1336, 10.1137/S1064827597319519

10.1007/s006070050015

10.6028/jres.049.044

Rudi, 2017, Advances in Neural Information Processing Systems 30, 3888

Ullah, 2018, Advances in Neural Information Processing Systems 31, 7311

Liberty, E. (2009), Accelerated dense random projections. PhD thesis, Computer Science, Yale University.

Simchowitz, M. , Alaoui, A. E. and Recht, B. (2017), On the gap between strict-saddles and true convexity: An Omega $(\log d)$ lower bound for eigenvector approximation. arXiv:1704.04548

10.1215/S0012-7094-42-00908-6

10.1007/978-3-642-15007-4

10.1109/FOCS.2013.21

Davidson, 2001, Handbook of the Geometry of Banach Spaces, I, 317, 10.1016/S1874-5849(01)80010-3

Demmel, 2007, ‘Fast linear algebra is stable, Numer. Math., 108, 59, 10.1007/s00211-007-0114-x

10.1006/jcss.2000.1711

Alaoui, 2015, Advances in Neural Information Processing Systems 28, 775

10.1090/pcms/025/01

Schölkopf, B. , Smola, A. and Müller, K.-R. (1996), Nonlinear component analysis as a kernel eigenvalue problem. Technical report 44, Max-Planck-Institut für biologische Kybernetik.

Fierro, 1999, ‘UTV tools: Matlab templates for rank-revealing UTV decompositions, Numer. Algorithms, 20, 165, 10.1023/A:1019112103049

Oymak, 2018, ‘Universality laws for randomized dimension reduction, with applications, Inf. Inference, 7, 337, 10.1093/imaiai/iax011

Parlett, B. N. (1998), The Symmetric Eigenvalue Problem, corrected reprint of the 1980 original, Vol. 20 of Classics in Applied Mathematics, SIAM.

10.1109/FOCS.2006.37

Moulines, 2011, Advances in Neural Information Processing Systems 24, 451

Woodruff, 2014, ‘Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci., 10, 1, 10.1561/0400000060

10.1016/0003-4916(89)90322-9

10.1016/j.spasta.2018.02.002

Krahmer, 2011, ‘New and improved Johnson–Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 1269, 10.1137/100810447

Nyström, 1930, ‘Über Die Praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben, Acta Math., 54, 185, 10.1007/BF02547521

10.1145/1219092.1219097

Martinsson, P.-G. , Quintana-Ortí, G. , Heavner, N. and van de Geijn, R. (2015), Householder QR factorization with randomization for column pivoting (HQRRP). arXiv:1512.02671

10.1145/355945.355946

10.1137/17M1111590

10.1287/moor.1100.0456

10.1137/16M1074941

Lopez-Paz, 2014, 31st International Conference on Machine Learning, 32, 1359

10.1137/S0895479892241913

10.1109/ICASSP.2010.5495812

Hennig, P. and Osborne, M. A. (2019), probabilistic-numerics.org

10.1016/j.aml.2019.03.024

Musco, 2015, Advances in Neural Information Processing Systems 28, 1396

Le, 2013, 30th International Conference on Machine Learning, 28, 244

Parker, D. S. (1995), Random butterfly transformations with applications in computational linear algebra. Report CSD-950023, UCLA.

10.1109/18.985947

Kueng, 2019, 2-designs minimize variance of trace estimators

Fine, 2001, ‘Efficient SVM training using low-rank kernel representation, J. Mach. Learn. Res., 2, 243

10.1137/0720053

Li, 2015, ‘Large-scale Nyström kernel matrix approximation using randomized SVD, IEEE Trans. Neural Networks Learning Syst., 26, 152, 10.1109/TNNLS.2014.2359798

10.1090/pcms/025/04

10.1137/S0895479803436202

Kyng, R. (2017), Approximate Gaussian elimination. ProQuest LLC, Ann Arbor, MI. PhD thesis, Yale University.

Gionis, 1999, 25th International Conference on Very Large Data Bases (VLDB ’99), 518

Bach, 2013, 26th Annual Conference on Learning Theory, 30, 185

10.1109/TPAMI.2015.2448083

Charikar, 2004, ‘Finding frequent items in data streams, Theoret. Comput. Sci., 312, 3, 10.1016/S0304-3975(03)00400-6

Feldman, 2016, Advances in Neural Information Processing Systems 29, 2766

Lust-Piquard, 1986, ‘Inégalités de Khintchine dans ${C}_p\left(1\lt p\lt \infty \right)$, C.R. Acad. Sci. Paris Sér. I Math., 303, 289

Davis, 2016, Acta Numerica, 25, 383

Gopal, A. and Martinsson, P.-G. (2018), The PowerURV algorithm for computing rank-revealing full factorizations. arXiv:1812.06007

10.1007/BF01452844

Richtárik, 2020, ‘Stochastic reformulations of linear systems: Algorithms and convergence theory, SIAM J. Matrix Anal. Appl., 41, 487, 10.1137/18M1179249

10.1016/j.neucom.2019.06.070

Duersch, J. A. and Gu, M. (2015), True BLAS-3 performance QRCP using random sampling. arXiv:1509.06820v1

Yu, 2017, International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’17)

10.1002/mma.759

10.1137/140989546

10.1016/j.acha.2011.05.001

Dobriban, 2019, Advances in Neural Information Processing Systems 32, 3675

10.1137/140978430

Whaley, 1998, 1998 ACM/IEEE Conference on Supercomputing (SC ’98), 1

Achlioptas, 2001, 33rd Annual ACM Symposium on Theory of Computing, 611, 10.1145/380752.380858

Baboulin, 2014, International Conference on High Performance Computing for Computational Science (VECPAR 2014), 8969, 135

10.1016/j.acha.2007.12.002

10.1145/2814566

10.1109/IPDPS.2017.21

Xiao, 2017, 2017 IEEE 24th International Conference on High Performance Computing (HiPC), 233, 10.1109/HiPC.2017.00035

10.1137/12087116X

Mahoney, 2011, ‘Randomized algorithms for matrices and data, Found. Trends Mach. Learn., 3, 123

Lopes, 2019, ‘Estimating the algorithmic variance of randomized ensembles via the bootstrap, Ann. Statist., 47, 1088, 10.1214/18-AOS1707

10.1145/290200.287637

Duersch, 2017, ‘Randomized QR with column pivoting, SIAM J. Sci. Comput., 39, C263, 10.1137/15M1044680

Martinsson, P.-G. (2008), Rapid factorization of structured matrices via randomized sampling. arXiv:0806.2339

Bach, 2017, ‘On the equivalence between kernel quadrature rules and random feature expansions, J. Mach. Learn. Res., 18, 1

Cullum, 1974

10.1137/0917055

10.1137/S0097539704442684

Stewart, 1994, Numerical Analysis 1993, 303, 225

10.1007/BF02165411

10.1002/cpa.20227

Li, 2014, 25th Annual ACM–SIAM Symposium on Discrete Algorithms, 1562

Girard, 1989, ‘A fast “Monte Carlo cross-validation” procedure for large least squares problems with noisy data, Numer. Math., 56, 1, 10.1007/BF01395775

10.1007/978-94-017-3515-5

Muthukrishnan, 2005, ‘Data streams: Algorithms and applications, Found. Trends Theor. Comput. Sci., 1, 117, 10.1561/0400000002

10.1137/130949117

Cohen, 2016, 27th Annual ACM–SIAM Symposium on Discrete Algorithms, 278

Kac, 1956, Third Berkeley Symposium on Mathematical Statistics and Probability, 1954–1955, III, 171

10.5802/smai-jcm.24

Ghashami, 2016, 19th International Conference on Artificial Intelligence and Statistics, 51, 1365

10.1007/978-0-8176-4815-2

Boucheron, 2013, Concentration Inequalities: A Nonasymptotic Theory of Independence, 10.1093/acprof:oso/9780199535255.001.0001

10.1016/j.acha.2017.04.002

Malik, O. A. and Becker, S. (2019), Guarantees for the Kronecker fast Johnson–Lindenstrauss transform using a coherence and sampling argument. arXiv:1911.08424

10.1137/19M1257792

10.1007/s10444-016-9494-8

10.1007/0-387-24273-2_6

Martinsson, 2016, ‘A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices, SIAM J. Sci. Comput., 38, S485, 10.1137/15M1026080

Gower, 2018, Advances in Neural Information Processing Systems 31, 1619

Thrampoulidis, C. , Oymak, S. and Hassibi, B. (2014), The Gaussian min-max theorem in the presence of convexity. arXiv:1408.4837

10.1137/080731992

Fitzsimons, 2018, Uncertainty in Artificial Intelligence: Proceedings of the Thirty-Fourth Conference

10.1016/j.jat.2012.01.008

Musco, 2017, Advances in Neural Information Processing Systems 30, 3833

McCoy, 2014, ‘From Steiner formulas for cones to concentration of intrinsic volumes, Discrete Comput. Geom., 51, 926, 10.1007/s00454-014-9595-4

Wang, 2019, ‘Scalable kernel $k$ -means clustering with Nyström approximation: Relative-error bounds, J. Mach. Learn. Res., 20, 431

Muirhead, 1982, Aspects of Multivariate Statistical Theory, 10.1002/9780470316559

10.1007/BF01200757

Cohen, 1999, ‘Approximating matrix multiplication for pattern recognition tasks, J. Algorithms, 30, 211, 10.1006/jagm.1998.0989

Clarkson, 2013, 2013 ACM Symposium on Theory of Computing (STOC ’13), 81

Kahan, 1966, ‘Numerical linear algebra, Canad. Math. Bull., 9, 757, 10.4153/CMB-1966-083-2

Strang, 2019, Linear Algebra and Learning from Data

Kannan, 2017, Acta Numerica, 26, 95

10.1007/BF00275687

Bartlett, P. (2013), U-statistics. Berkeley Statistics 210B Lecture Notes.

Stewart, 1998, Basic Decompositions, 1

Golub, 2013, Matrix Computations, 10.56021/9781421407944

10.1137/080734029

10.2172/674849

10.1016/j.cma.2015.02.006

10.1002/(SICI)1099-1506(199805/06)5:3<147::AID-NLA128>3.0.CO;2-2

Drineas, 2006, ‘Fast Monte Carlo algorithms for matrices, III: Computing a compressed approximate matrix decomposition, SIAM J. Comput., 36, 184, 10.1137/S0097539704442702

Dao, 2019, 36th International Conference on Machine Learning, 97, 1517

Marcus, 1981, Random Fourier Series with Applications to Harmonic Analysis, 101

10.1137/120866580

Kar, 2012, 15th International Conference on Artificial Intelligence and Statistics, 22, 583

Tropp, J. A. (2019), Matrix concentration and computational linear algebra. CMS Lecture Notes 2019-01, Caltech, Pasadena, CA.

10.1145/2487575.2487591

Gu, 2015, ‘Subspace iteration randomization and singular value problems, SIAM J. Sci. Comput., 37, A1139, 10.1137/130938700

Urano, Y. (2013), A fast randomized algorithm for linear least-squares regression via sparse transforms. Master’s thesis, New York University.

Bach, 2005, 22nd International Conference on Machine Learning (ICML ’05), 33, 10.1145/1102351.1102356

10.1145/3313276.3316363

10.1137/18M1201068

Kumar, 2012, ‘Sampling methods for the Nyström method, J. Mach. Learn. Res., 13, 981

10.1145/1536414.1536445

10.1214/16-AAP1195

Golub, 1977, Mathematical Software III (Proceedings of a Symposium Conducted by the Mathematics Research Center, the University of Wisconsin–Madison), 361

Golub, 1994, Numerical Analysis 1993, 303, 105

10.1016/j.acha.2015.02.003

10.1137/17M1137541

Boutsidis, 2016, 48th Annual ACM Symposium on Theory of Computing, 236

10.1137/1.9781611976045

10.1007/s00039-015-0332-9

Hamid, 2014, 31st International Conference on Machine Learning, 32, 19

10.1109/ISIT.2015.7282516

10.1214/aos/1009210544

Rahimi, 2008, Advances in Neural Information Processing Systems 20, 1177

10.1137/030602678

10.1137/16M1104974

Carmon, 2019, 32nd Conference on Learning Theory, 99, 589

Wang, S. (2019), Simple and almost assumption-free out-of-sample bound for random feature mapping. arXiv:1909.11207

Grimmett, 2001, Probability and Random Processes, 10.1093/oso/9780198572237.001.0001

10.1109/FOCS.2016.68

Jin, R. , Kolda, T. G. and Ward, R. (2019), Faster Johnson–Lindenstrauss transforms via Kronecker products. arXiv:1909.04801

Carl, 1985, ‘Inequalities of Bernstein–Jackson-type and the degree of compactness of operators in Banach spaces, Ann. Inst. Fourier (Grenoble), 35, 79, 10.5802/aif.1020

10.1214/08-AAP550

10.1145/2493252.2493254

10.1007/0-387-24273-2_4

Szabó, 2019, 22nd International Conference on Artificial Intelligence and Statistics, 89, 827

10.1007/s00453-016-0205-0

Ghashami, 2016, ‘Frequent directions: Simple and deterministic matrix sketching, SIAM J. Comput., 45, 1762, 10.1137/15M1009718

Li, 2015, ‘Butterfly factorization, Multiscale Model. Simul., 13, 714, 10.1137/15M1007173

10.1109/ICASSP.2006.1660793

Kurz, 2002, ‘The adaptive cross-approximation technique for the 3D boundary-element method, IEEE Trans. Magnetics, 38, 421, 10.1109/20.996112

10.1137/1.9781611970319

Avron, H. (2018), Randomized Riemannian preconditioning for quadratically constrained problems. Slides, Workshop on Randomized Numerical Linear Algebra, Simons Institute, UC Berkeley.

10.1137/080734339

10.1137/100786617

Needell, 2014, Advances in Neural Information Processing Systems 27, 1017

10.1006/jcss.2001.1813

10.1561/2200000048

Kong, 2017, ‘Spectrum estimation from samples, Ann. Statist., 45, 2218, 10.1214/16-AOS1525

Alon, 1999, ‘The space complexity of approximating the frequency moments, J. Comput. System Sci., 58, 137, 10.1006/jcss.1997.1545

Lin, 2011, ‘Fast construction of hierarchical matrix representation from matrix–vector multiplication, J. Comput. Phys., 230, 4071, 10.1016/j.jcp.2011.02.033

10.1007/978-0-8176-4948-7

Mezzadri, 2007, ‘How to generate random matrices from the classical compact groups, Notices Amer. Math. Soc., 54, 592

10.1016/0021-9991(87)90140-9

Pillai, 2017, ‘Kac’s walk on $n$ -sphere mixes in $n\log n$ steps, Ann. Appl. Probab., 27, 631, 10.1214/16-AAP1214

Boutsidis, 2009, 20th Annual ACM–SIAM Symposium on Discrete Algorithms, 968

10.1137/090771806

10.1007/978-1-4419-0661-8

10.1007/11830924_30

Martinsson, P.-G. (2015), Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting. arXiv:1505.08115

10.1007/978-3-642-13562-0_2

10.1137/090767911

10.1038/324446a0

10.1137/040616413

10.1214/aop/1176988864

10.1137/15M1016679

Samo, Y.-L. K. and Roberts, S. (2015), Generalized spectral kernels. arXiv:1506.02236

Edelman, A. S. (1989), Eigenvalues and condition numbers of random matrices. ProQuest LLC, Ann Arbor, MI. PhD thesis, Massachusetts Institute of Technology.

Chen, 2019, 32nd Conference on Learning Theory, 99, 663

Rudi, 2017, Advances in Neural Information Processing Systems 30, 3215

10.1093/imaiai/iau005

Tropp, J. A. (2018), Analysis of randomized block Krylov methods. Under revision.

10.1145/1039488.1039494

10.1137/15M1032909

Ross, 2011, ‘Fundamentals of Stein’s method, Probab. Surv., 8, 210, 10.1214/11-PS182

Bai, 1987, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (Software, Environments and Tools)

10.1145/3004053

Indyk, 1999, 30th Annual ACM Symposium on Theory of Computing (STOC ’98), 604

Thurau, 2012, 2012 SIAM International Conference on Data Mining, 684, 10.1137/1.9781611972825.59

The Numerical Algorithms Group (NAG) (2019), The NAG Library Mark 27. https://www.nag.com/content/naglibrary-mark27

10.1073/pnas.0803205106

Upadhyay, J. (2016), Fast and space-optimal low-rank factorization in the streaming model with application in differential privacy. arXiv:1604.01429

Achlioptas, 2003, ‘Database-friendly random projections: Johnson–Lindenstrauss with binary coins, J. Comput. System Sci., 66, 671, 10.1016/S0022-0000(03)00025-4

Briggs, 1995, The DFT: An Owner’s Manual for the Discrete Fourier Transform, 10.1137/1.9781611971514

10.1137/16M1081270

Yu, 2017, Single-pass PCA of large high-dimensional data, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17), 3350

McCoy, M. B. and Tropp, J. A. (2013), The achievable performance of convex demixing. ACM Technical Report 2017-02, Caltech.

10.1073/pnas.0804869105

10.1017/9781108231596

Sloane, 1983, Cryptography (Burg Feuerstein, 1982), 149, 71

10.1016/0024-3795(93)90493-8

10.1137/0613066

10.1137/18M1189749

10.1137/15M1025487

10.1137/15M1040827

10.1214/aos/1176343757

10.1137/100804139

10.2140/camcos.2006.1.133

Oliveira, R. I. (2009 a), Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges. arXiv:0911.0600

10.1553/etna_vol51s469

Chandrasekaran, 2012, ‘The convex geometry of linear inverse problems, Found. Comput. Math., 12, 805, 10.1007/s10208-012-9135-7

Van Handel, R. (2016), Probability in high dimension. APC 550 Lecture Notes, Princeton University.

10.1007/s10208-013-9142-3

Gittens, A. (2013), Topics in Randomized Numerical Linear Algebra. ProQuest LLC, Ann Arbor, MI. PhD thesis, California Institute of Technology.

Porod, 1996, ‘The cut-off phenomenon for random reflections, Ann. Probab., 24, 74, 10.1214/aop/1042644708

Meng, 2013, 2013 ACM Symposium on Theory of Computing (STOC ’13), 91

Williams, 2001, Advances in Neural Information Processing Systems 13, 682

10.1007/s10208-011-9099-z

10.1006/jfan.1998.3384

10.1016/j.jcp.2004.10.033

10.1145/3242670

10.1016/j.aim.2012.08.010

Ailon, 2009, ‘The fast Johnson–Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39, 302, 10.1137/060673096

10.1145/1255443.1255449

Rudi, 2015, Advances in Neural Information Processing Systems 28, 1657

Drineas, 2005, ‘On the Nyström method for approximating a Gram matrix for improved kernel-based learning, J. Mach. Learn. Res., 6, 2153

Rokhlin, 2009, ‘A randomized algorithm for principal component analysis, SIAM J. Matrix Anal. Appl., 31, 1100, 10.1137/080736417

Ailon, 2006, 38th Annual ACM Symposium on Theory of Computing, 557

Rudi, 2018, Advances in Neural Information Processing Systems 31, 5672

Demmel, 2015, ‘Communication avoiding rank revealing QR factorization with column pivoting, SIAM J. Matrix Anal. Appl., 36, 55, 10.1137/13092157X

10.1137/16M1105396

Zouzias, A. (2013), Randomized primitives for linear algebra and applications. PhD thesis, University of Toronto.

10.1016/j.laa.2017.04.007

Schölkopf, 2001, Learning with Kernels, 10.7551/mitpress/4175.001.0001

Kyng, 2016, 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’16), 842

10.1002/cpe.4055

Tropp, 2017, Advances in Neural Information Processing Systems 30, 1225

Hackbusch, 2002, Lectures on Applied Mathematics, 9

10.1016/j.laa.2012.12.022

Horn, 2013, Matrix Analysis

Sriperumbudur, 2015, Advances in Neural Information Processing Systems 28, 1144

Martinsson, P.-G. and Tropp, J. (2020), Randomized numerical linear algebra: Foundations and algorithms. arXiv:2002.01387

10.1142/9789812836021_0015

Neal, 1996, Priors for Infinite Networks, 29

10.1007/s00041-008-9030-4