Past, Present and Future of Randomized Numerical Linear Algebra I

on YouTube ↗01h 27m

" summary

Randomized sketches replace heavy SVDs by sampling columns/rows or by applying subsampled Hadamard or sign matrices, then uniform sampling; matrix multiplication is approximated by CR = AS S^T B with Frobenius error O((||A||_F||B||_F)/√c) and spectral guarantees when c ≳ stable rank·polylog. Column selection uses leverage scores (top-k right singular vectors) and yields (1+ε) CX approximations with O(k/ε^2 log(k/ε)) columns; later work cuts this to 3k/ε columns and toward k/ε. Implementations beat LAPACK by ~4× and scale to terabytes on cloud.

AI-written summary · about

" chapters (23)

1. 0:00Start
2. 3:42RandNLA: sampling rows/columns
3. 6:24Interplay
4. 7:03Roadmap of the tutorial
5. 8:35Areas of RandNLA that will not be covered in this tutorial
6. 10:48Human genetics
7. 20:22Issues (cont'd)
8. 20:53SVD decomposes a matrix as...
9. 24:38Our objective for the CX decomposition
10. 29:00A sampling approach
11. 29:39The algorithm (matrix notation)
12. 30:26The algorithm (matrix notation, cont'd)
13. 32:24Simple Lemmas
14. 33:00A bound for the Frobenius norm
15. 37:16Using a dense S (instead of a sampling matrix..)
16. 39:09Using a dense S (instead of a sampling matrix...)
17. 42:08Using a dense 5 (cont'd)
18. 44:18Recap: approximating matrix multiplication
19. 49:20Back to the CX decomposition
20. 51:23Proof (spectral norm), cont'd
21. 53:23Relative-error Frobenius norm bounds
22. 55:23Subspace sampling (Frobenius norm)
23. 57:09Towards a relative error bound...

" related talks

• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 01h 04mSketching and Randomized Linear AlgebraDavid P. Woodruff · Sublinear Algorithms Boot Camp 2024
• 01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel MethodsKen Clarkson · Foundations of Data Science Boot Camp 2018
• 29mImplementing Randomized Matrix Algorithms in Parallel and Distributed EnvironmentsMichael Mahoney · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 2024