Randomized Numerical Linear Algebra

on YouTube ↗48m

" summary

Randomized row/column sampling with R = Θ(d/ε) scaled rows gives 1+ε relative‑error solutions to overconstrained least‑squares by sampling with leverage scores computed from a low‑rank SVD or an approximate basis, and leverage scores for graph incidence matrices equal effective resistances = leverage scores which yields spectral sparsifiers. Column selection for CX factorization needs about C = Θ(k log k) sampled columns to approximate the best rank‑k projection. Practical costs are roughly O(nd/ε) to approximate leverage scores, plus matrix Chernoff/Bernstein concentration for correctness.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 4:50The p's: leverage scores
3. 5:46The pi's: leverage scores
4. 7:17Leverage scores: tall & thin matrices
5. 8:36Leverage scores: short & fat matrices
6. 9:41Leverage scores: general case
7. 11:15Other ways to create matrix sketches
8. 13:09Applications of leverage scores
9. 14:05Why do they work?
10. 16:46Computing leverage scores
11. 20:12Least-squares problems
12. 21:20Exact solution to L2 regression
13. 22:04Algorithm: Sampling for L2 regression
14. 22:48Theorem
15. 23:36Algorithm: Sampling for least squares
16. 24:34SVD decomposes a matrix as...
17. 26:26The CX decomposition
18. 28:14The algorithm
19. 28:58Relative-error Frobenius norm bounds
20. 30:12Leverage scores: human genetics data
21. 33:19Leverage scores & Laplacians
22. 34:23Leverage scores & effective resistances
23. 37:14Running time issues
24. 38:31Element-wise sampling
25. 42:12Conclusions

" related talks

• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 01h 31mPast, Present and Future of Randomized Numerical Linear Algebra IIMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 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)
• 32mRidge Regression and Deterministic Ridge Leverage Score SamplingShannon McCurdy · Randomized Numerical Linear Algebra and Applications 2018