Sharp Matrix Concentration

on YouTube ↗27m

" summary

Claims removal of the usual log^2 d loss for spectral-norm concentration of Gaussian random matrices by trading it for a concrete second-order covariance term — the spectral norm of Cov(vec X) — which measures non‑commutativity and is far easier to compute than Tropp’s XYXY quantity. Proofs use Gaussian integration-by-parts and moment/decoupling estimates, recover IID/GUE (no log) and diagonal (log needed) extremes, and give explicit bounds reducing prior log^{1/4} rates down to no extra log when the covariance term is small.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 1:01Motivation
3. 5:28Quantify Non-Commutativity
4. 16:31The Covariance Matrix

" related talks

• 23mHow Large is the Norm of a Random Matrix?Ramon van Handel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 34mMatrix Martingales in Randomized Numerical Linear AlgebraRasmus Kyng · Randomized Numerical Linear Algebra and Applications 2018
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 04mUser-Friendly Tools for Random Matrices IJoel Tropp · Big Data Boot Camp 2013
• 01h 00mLog-concave Polynomials and Spectral Independence 2Kuikui Liu · Analysis and TCS Boot Camp 2023
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event