How Large is the Norm of a Random Matrix?

on YouTube ↗23m

" summary

Gives matching upper and lower bounds for the expected spectral norm of an independent-entry Gaussian matrix in terms of two explicit parameters: the row-variance scale and the maximal entry scale, roughly sigma + sigma_ sqrt(log N). Proof uses Gaussian Poincaré/Khinchin for lower bounds and a novel compression-based upper bound (not standard matrix concentration), requires independent entries* and mild non-multiscale variance distribution. Applications: sharp stochastic block model and random Laplacian estimates, useful for matrix completion.

AI-written summary · about

" chapters (5)

1. 0:00Introduction to Random Matrices
2. 10:52Limitations of Current Bounds
3. 13:22New Structured Matrix Results
4. 20:34Open Questions and Future Work
5. 21:42Applications and Conclusion

" related talks

• 27mSharp Matrix ConcentrationMarch Boedihardjo · Deep Learning Theory Symposium 2021
• 01h 04mUser-Friendly Tools for Random Matrices IJoel Tropp · Big Data Boot Camp 2013
• 45mUser-Friendly Tools for Random Matrices IIIJoel Tropp · Big Data Boot Camp 2013
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 36mThe Rank of Sparse Random MatricesJane Gao · Computational Phase Transitions (Simons Institute, 2020)
• 19mThe Spectrum of Nonlinear Random Matrices for Ultra-Wide Neural NetworksYizhe Zhu · Deep Learning Theory Symposium 2021
• 57mUser-Friendly Tools for Random Matrices IIJoel Tropp · Big Data Boot Camp 2013
• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs