Universality of Approximate Message Passing on Semi-random Matrices

on YouTube ↗58m

" summary

Claim: AMP iterates on semi‑random matrices M = S Ψ S (diagonal ±1 signing with deterministic Ψ that is delocalized and ΨΨᵀ ≈ σ²I entrywise) produce the same empirical Gaussian limits and state‑evolution as classical Gaussian/orthogonally invariant models. Proof uses Hermite‑polynomial moment expansion, combinatorial decorated‑tree pruning to capture cancellations, and method‑of‑moments concentration; simulations compare spike‑and‑sine vs Haar and show matching MSE curves. Requires smooth nonlinearities, signing assumption, and (for estimator transfer) strong convexity.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 1:06A motivating simulation
3. 10:02Approximate Message Passing: Introduction
4. 11:53Approximate Message Passing: Properties
5. 13:00Approximate Message Passing distributional assumptions
6. 15:11Approximate Message Passing general philosophy
7. 19:41Universality: what is known?
8. 24:20Goals
9. 25:38Memory-free AMP algorithms
10. 27:58Semi-random matrices
11. 30:58The universality result
12. 33:32Example 1
13. 35:03Example 3
14. 38:15Proof techniques
15. 39:43Step 2
16. 42:42Step 3a: Concentration
17. 43:17Step 3b: Handling the expectation
18. 44:00Step 3b: Simple example
19. 44:44Step 3b: Expectation evaluation
20. 45:18Step 3b: Controlling the expectation
21. 48:23Parallel work: Wang, Zhong and Fan (2022)
22. 51:27Regularized Least Squares: Universality Classes
23. 52:35Regularized Least Squares: Guarantees
24. 53:52Conclusion

" related talks

• 49mApproximate Message Passing Algorithms For Orthogonally Invariant ModelsZhou Fan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 31mIncremental Approximate Message PassingAhmed El Alaoui · Computational Phase Transitions (Simons Institute, 2020)
• 27mThe Estimation Error of General First Order MethodsMichael Celentano · Rigorous Evidence for Information-Computation Trade-offs
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 37mSparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial CouplingFlorent Krzakala · Coding: From Practice to Theory
• 46mSolvable Model of Unsupervised Feature LearningLenka Zdeborova · Random Instances and Phase Transitions (Simons Institute, 2016)
• 29mAre Generative Models The New Sparsity?Bruno Loureiro · Rigorous Evidence for Information-Computation Trade-offs