# Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2017.

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

- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Hessian Eigenspectra of More Realistic Nonlinear Models](https://mlsanity.com/paper/2103.01519/) (2021)
- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [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)
- [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula](https://mlsanity.com/paper/2502.20003/) (2025)
- [Fundamental limits to learning closed-form mathematical models from data](https://mlsanity.com/paper/2204.02704/) (2022)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [Bayesian Inversion for Nonlinear Imaging Models using Deep Generative Priors](https://mlsanity.com/paper/2203.10078/) (2022)
- [Optimal scaling laws in learning hierarchical multi-index models](https://mlsanity.com/paper/2602.05846/) (2026)
- [Optimal Algorithms for the Inhomogeneous Spiked Wigner Model](https://mlsanity.com/paper/2302.06665/) (2023)
- [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)
- [The Role of the Time-Dependent Hessian in High-Dimensional Optimization](https://mlsanity.com/paper/2403.02418/) (2024)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles](https://mlsanity.com/paper/2101.07464/) (2021)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Spectral Phase Transition and Optimal PCA in Block-Structured Spiked models](https://mlsanity.com/paper/2403.03695/) (2024)
- [Compressing Sign Information in DCT-based Image Coding via Deep Sign Retrieval](https://mlsanity.com/paper/2209.10712/) (2022)
- [Fast and Robust Phase Retrieval via Deep Expectation-Consistent Approximation](https://mlsanity.com/paper/2407.09687/) (2024)
- [Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks](https://mlsanity.com/paper/2510.18435/) (2025)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)
- [Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Models](https://mlsanity.com/paper/2512.19334/) (2025)

## Abstract (arXiv)

In phase retrieval we want to recover an unknown signal boldsymbol x∈mathbb Cd from n quadratic measurements of the form yi = |langleboldsymbol ai,boldsymbol xrangle|2+wi where boldsymbol ai∈ mathbb Cd are known sensing vectors and wi is measurement noise. We ask the following weak recovery question: what is the minimum number of measurements n needed to produce an estimator hatboldsymbol x(boldsymbol y) that is positively correlated with the signal boldsymbol x? We consider the case of Gaussian vectors boldsymbol ai. We prove that - in the high-dimensional limit - a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For n≤ d-o(d) no estimator can do significantly better than random and achieve a strictly positive correlation. For n≥ d+o(d) a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theory arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper and lower bound generalize beyond phase retrieval to measurements yi produced according to a generalized linear model. As a byproduct of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.