# Phase retrieval in high dimensions: Statistical and computational phase transitions

arXiv: https://arxiv.org/abs/2006.05228 · HTML: https://mlsanity.com/paper/2006.05228/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 30 of 39)

- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD](https://mlsanity.com/paper/2305.18502/) (2023)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula](https://mlsanity.com/paper/2502.20003/) (2025)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?](https://mlsanity.com/paper/2205.10009/) (2022)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models](https://mlsanity.com/paper/2502.16849/) (2025)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression](https://mlsanity.com/paper/2402.13622/) (2024)
- [The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures](https://mlsanity.com/paper/2410.05609/) (2024)
- [Bayes-optimal limits in structured PCA, and how to reach them](https://mlsanity.com/paper/2210.01237/) (2022)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Fast and Robust Phase Retrieval via Deep Expectation-Consistent Approximation](https://mlsanity.com/paper/2407.09687/) (2024)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Joint Learning in the Gaussian Single Index Model](https://mlsanity.com/paper/2505.21336/) (2025)

## Abstract (arXiv)

We consider the phase retrieval problem of reconstructing a n-dimensional real or complex signal Xstar from m (possibly noisy) observations Yμ = | sumi=1n Phiμ i Xstari/√n|, for a large class of correlated real and complex random sensing matrices Phi, in a high-dimensional setting where m,n→∞ while α = m/n=Theta(1). First, we derive sharp asymptotics for the lowest possible estimation error achievable statistically and we unveil the existence of sharp phase transitions for the weak- and full-recovery thresholds as a function of the singular values of the matrix Phi. This is achieved by providing a rigorous proof of a result first obtained by the replica method from statistical mechanics. In particular, the information-theoretic transition to perfect recovery for full-rank matrices appears at α=1 (real case) and α=2 (complex case). Secondly, we analyze the performance of the best-known polynomial time algorithm for this problem -- approximate message-passing -- establishing the existence of a statistical-to-algorithmic gap depending, again, on the spectral properties of Phi. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.