Phase Transitions in Low-Rank Matrix Estimation

on YouTube ↗45m

" summary

Focuses on low-rank matrix estimation problems, describing phase transitions and algorithmic-to-information gaps that occur when recovering matrices from noisy or incomplete observations. Covers Bayesian approaches, connections with statistical physics (spin-glass-type analyses), and how these tools predict thresholds and performance of inference algorithms for specific low-rank matrix models.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 1:37LOW-RANK MATRIX ESTIMATION
3. 2:33SOME EXAMPLES...
4. 6:20PROBABILISTIC SETTING
5. 8:28OUTLINE
6. 9:04AMP FOR GAUSSIAN ADDITIVE CHANNEL AWGN
7. 10:56STATE EVOLUTION Single letter characterization of the AMP
8. 12:00REPLICA MUTUAL INFORMATION
9. 18:15FORMULAS FOR UVT AMP
10. 18:53CHANNEL UNIVERSALITY
11. 22:13MINIMUM MEAN-SQUARED ERROR
12. 24:06TWO PHASE TRANSITIONS FOR R 4
13. 27:56NON-SYMMETRIC COMMUNITY DETECTION
14. 29:56CLUSTERING MIXTURES OF GAUSSIANS IN HIGH DIMENSIONS
15. 31:37WHAT ABOUT RANK 1 SPARSE PCA?
16. 33:49EASY, HARD AND IMPOSSIBLE INFERENCE
17. 35:35SKETCH OF THE PROOF
18. 41:36CONCLUSIONS

" related talks

• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 39mPhase Retrieval in High Dimensions: Statistical and Computational Phase TransitionsFlorent Krzakala · Computational Phase Transitions (Simons Institute, 2020)
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 35mThresholds of Descending Algorithms in Inference ProblemsStefano Sarao Mannelli · Computational Phase Transitions (Simons Institute, 2020)
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 36mTo Be (Hard) or Not Be:...Florent Krzakala · Rigorous Evidence for Information-Computation Trade-offs
• 37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?Rachel Ward · Optimization, Statistics and Uncertainty