Randomized numerical linear algebra: Foundations and algorithms
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.
© 2020 The Author(s). Published by Cambridge University Press. Published online by Cambridge University Press: 30 November 2020. We are grateful to Arieh Iserles for proposing that we write this survey. Both authors have benefited greatly from our collaborations with Vladimir Rokhlin and Mark Tygert. Most of all, we would like to thank Richard Kueng for his critical reading of the entire manuscript, which has improved the presentation in many places. Madeleine Udell, Riley Murray, James Levitt and Abinand Gopal also gave us useful feedback on parts of the paper. Lorenzo Rosasco offered invaluable assistance with the section on kernel methods for machine learning. Navid Azizan, Babak Hassibi and Peter Richtárik helped with citations to the literature on SGD. Finally, we would like to thank our ONR programme managers, Reza Malek-Madani and John Tague, for supporting research on randomized numerical linear algebra. JAT acknowledges support from the Office of Naval Research (awards N-00014-17-1-2146 and N-00014-18-1-2363). PGM acknowledges support from the Office of Naval Research (award N00014-18-1-2354), from the National Science Foundation (award DMS-1620472) and from Nvidia Corp.
Submitted - 2002.01387.pdf