Matrix Martingales in Randomized Numerical Linear Algebra

on YouTube ↗34m

" summary

Matrix martingale concentration (a matrix Freedman bound) controls the predictable quadratic variation so randomized incomplete Gaussian elimination yields a sparse factor U with U^T U ≈ L after isotropic normalization. The algorithm does random vertex elimination and samples the induced clique instead of materializing it; expected decomposition equals the original Laplacian and martingale concentration (variance per round scales like 1/remaining‑vertices, giving a harmonic log factor) proves a constant‑factor spectral approximation in M log^3 n time.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:49Matrix Martingales in Randomized Numerical Linear Algebra
3. 1:00Concentration of Scalar Random Variables
4. 2:21Concentration of Scalar Martingales
5. 6:05Concentration of Matrix Random Variables
6. 7:53Concentration of Matrix Martingales
7. 9:06Laplacian Matrices
8. 10:33Laplacian of a Graph
9. 12:02Solving a Laplacian Linear Equation
10. 14:40Additive View of Gaussian Elimination
11. 17:23Why is Gaussian Elimination Slow?
12. 20:18Approximate Gaussian Elimination
13. 21:14Approximating Matrices by Sampling
14. 21:45Approximating Matrices in Expectation
15. 24:22Approximation?
16. 25:31Essential Tools
17. 26:20Matrix Concentration: Edge Variables
18. 26:56Predictable Quadratic Variation
19. 28:08Sample Variance
20. 30:55Summary

" related talks

• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 01h 31mPast, Present and Future of Randomized Numerical Linear Algebra IIMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 27mSharp Matrix ConcentrationMarch Boedihardjo · Deep Learning Theory Symposium 2021
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 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 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018