The Rank of Sparse Random Matrices

on YouTube ↗36m

" summary

Three random-matrix models (a sparse k-nonzeros per row model, a degree-prescribed simple/flexible models, and a general-field version) have typical rank(A)/n = 1 − sup_{α∈[0,1]} Φ(α) where Φ is built from the PGFs of row/column degrees; the earlier upper bound becomes exact and the result is essentially field-insensitive. Proof uses the peeling two-core analysis to reduce rank to core size, a cavity/coupling estimate of nullity via log |solution space|, and a pinning strategy to kill short relations; maxima at α=0 gives full row rank.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 0:37Overview
3. 0:55Simple Model
4. 1:56Flexible Model
5. 5:12Rank of Simple Model
6. 5:43Rank of Flexible Model
7. 8:35Literature Review
8. 10:58What is the maxima for
9. 13:25Rank of a
10. 16:49How the proof works
11. 18:24Properties of the noun space
12. 21:00The trick
13. 22:21The formula
14. 23:01The key features
15. 33:00Proof

" related talks

• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 01h 04mUser-Friendly Tools for Random Matrices IJoel Tropp · Big Data Boot Camp 2013
• 23mHow Large is the Norm of a Random Matrix?Ramon van Handel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 43mGeometric Complexity Theory and Tensor RankChristian Ikenmeyer · Geometric Complexity Theory 2014
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 59mElementary Results on Maximal, Generic and Typical RanksGrigoriy Blekherman · Tensors in Computer Science and Geometry 2014
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)