# Approximate Message Passing with Random Initialization for Phase Retrieval

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 85 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 18 of 18)

- [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)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Dynamical Decoupling of Generalization and Overfitting in Large Two-Layer Networks](https://mlsanity.com/paper/2502.21269/) (2025)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Phase Transitions for Feature Learning in Neural Networks](https://mlsanity.com/paper/2602.01434/) (2026)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit](https://mlsanity.com/paper/2511.15120/) (2025)
- [A non-asymptotic distributional theory of approximate message passing for sparse and robust regression](https://mlsanity.com/paper/2401.03923/) (2024)
- [Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning](https://mlsanity.com/paper/2602.02431/) (2026)
- [Optimal Sample Complexity of Subgradient Descent for Amplitude Flow via Non-Lipschitz Matrix Concentration](https://mlsanity.com/paper/2011.00288/) (2020)
- [Learning single index model with gradient descent: spectral initialization and precise asymptotics](https://mlsanity.com/paper/2509.23527/) (2025)
- [Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis](https://mlsanity.com/paper/2602.09959/) (2026)
- [Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow](https://mlsanity.com/paper/1905.09320/) (2019)

## Abstract (arXiv)

We analyze approximate message passing (AMP) with an independent Gaussian initialization for noiseless phase retrieval in the proportional asymptotic regime. A random initialization has overlap of order d-1/2 with the signal, and AMP requires a growing number of iterations to attain non-vanishing overlap. Thus, its precise behavior cannot be characterized by classical fixed-time state evolution. We prove a Gaussian decomposition of the AMP trajectory and control its error over the horizons required for recovery. The resulting analysis shows that random initialization attains the weak-recovery threshold δrm weak=1/2. For δ∈(δrm weak,δrm str), where δrm str≈1.13, the signal strength follows state evolution and approaches its stable finite fixed point uniformly for (n1/3/operatornamepolylog(n)) iterations. For δ>δrm str, AMP reaches any prescribed fixed recovery accuracy within Oδ,varepsilon(log n) iterations. The majority of our analysis applies more generally to generalized AMP for single-index models.