Approximate Message Passing Algorithms For Orthogonally Invariant Models

on YouTube ↗49m

" summary

Approximate Message Passing extends to W with Haar eigenvectors and arbitrary spectral law by replacing the usual Onsager terms with coefficients given by the R-transform/free cumulants of the spectral limit, yielding Gaussian state evolution for the debiased Z iterates. Derivations use HCIZ integrals and dynamic functional / inductive conditioning proofs tracking noncrossing-partition combinatorics. A K‑dimensional AMP with spectral initialization denoiser empirically beats PCA on correlated-noise simulations (Beta(3,1) example), and an AMP solving Parisi–Poders equations plus a conditional second moment proves replica‑symmetric free energy at high temperature.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:40Approximate Message Passing algorithms
3. 2:07Examples of AMP
4. 3:01Appeal of AMP
5. 5:28Outline
6. 6:11AMP algorithm for i.i.d. matrices
7. 9:30AMP algorithm for orthogonally invariant matrices
8. 13:49Emergence of the free cumulants
9. 20:44The memory free setting
10. 23:21Bayes PCA with correlated noise
11. 26:16K-dimensional AMP with spectral initialization
12. 29:07Bayes OAMP
13. 38:12Ising model with orthogonally invariant couplings
14. 40:33The replica-symmetric free energy
15. 41:22Conditional second moment idea
16. 42:55Memory-free AMP algorithm for solving TAP
17. 44:01The conditional analysis
18. 45:16Conclusion
19. 45:56References

" related talks

• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 01h 31mIncremental Approximate Message PassingAhmed El Alaoui · Computational Phase Transitions (Simons Institute, 2020)
• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 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
• 29mAre Generative Models The New Sparsity?Bruno Loureiro · Rigorous Evidence for Information-Computation Trade-offs