User-Friendly Tools for Random Matrices I

on YouTube ↗01h 04m

" summary

Shows that a sample covariance estimator is a sum of independent rank-one pieces and analyzes its spectral error with a Matrix Bernstein concentration bound. Under the boundedness assumption ||X||^2 ≤ B, the paper proves E||Â − A|| ≤ sqrt(2B||A|| log(2p)/n) + 2B log(2p)/(3n), so for typical B ≈ p one needs roughly n ≳ p log p / ε^2 samples for ε-accuracy. Result is near-sharp but pays a log factor and requires bounded tails.

AI-written summary · about

" chapters (6)

1. 0:00Introduction and context
2. 3:49History of random matrices
3. 10:54Applications and motivation
4. 20:53Models vs reality
5. 27:57Core principles of the approach
6. 34:23Sample covariance example

" related talks

• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 23mHow Large is the Norm of a Random Matrix?Ramon van Handel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 27mSharp Matrix ConcentrationMarch Boedihardjo · Deep Learning Theory Symposium 2021
• 36mThe Rank of Sparse Random MatricesJane Gao · Computational Phase Transitions (Simons Institute, 2020)
• 34mMatrix Martingales in Randomized Numerical Linear AlgebraRasmus Kyng · Randomized Numerical Linear Algebra and Applications 2018
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis