Phase Retrieval In High Dimensions: Statistical And Computational Phase Transitions

on YouTube ↗35m

" summary

Conjectures give an explicit replica symmetric potential whose maximizer yields the asymptotic MMSE; the formula is proven for Gaussian sensing matrices (real or complex) and for Gaussian priors with sensing = Gaussian × fixed matrix. Approximate message passing (GVAMP) is characterized by the same potential but often gets stuck in a hard phase (empirical gap between AMP and information-theoretic limits, e.g. AMP needs ~2.3 samples while unitary sensing shows an IT all‑or‑nothing threshold at α=2); strong recovery threshold equals β·R (β=1 real, 2 complex). A constructive optimal spectral method with preprocessor T(y)=1−1/y (noiseless case) is derived and empirically initializes cheap gradient descent to recover images for α≈3–4.

AI-written summary · about

" chapters (7)

1. 0:00Phase retrieval introduction
2. 7:12Replica formula and info limits
3. 12:12Algorithmic limits with AMP
4. 17:33Numerical analysis of thresholds
5. 21:05Optimal spectral methods
6. 29:57Summary and open problems
7. 30:40Q&A on spectral methods

" related talks

• 39mPhase Retrieval in High Dimensions: Statistical and Computational Phase TransitionsFlorent Krzakala · Computational Phase Transitions (Simons Institute, 2020)
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 49mApproximate Message Passing Algorithms For Orthogonally Invariant ModelsZhou Fan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 46mSolvable Model of Unsupervised Feature LearningLenka Zdeborova · Random Instances and Phase Transitions (Simons Institute, 2016)
• 45mPhase Transitions in Low-Rank Matrix EstimationFlorent Krzakala · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 14mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)