no. 16 · Tuesday 17 November 2026
Approximate Message Passing with Random Initialization for Phase Retrieval
Abstract
Randomly initialized first-order iterative algorithms are simple, widely used, and empirically effective across many high-dimensional inference problems, yet their theoretical behavior remains far less understood than that of algorithms started from more elaborate, problem-specific initializations such as spectral initialization. This paper takes a step toward closing this gap by studying randomly initialized approximate message passing (AMP) for noiseless phase retrieval, a canonical nonconvex inference problem. We give a non-asymptotic, growing-horizon characterization of the AMP trajectory from random initialization, and show that it achieves both the information-theoretic weak recovery threshold $δ_{\rm weak}=1/2$ and the AMP strong recovery threshold $δ_{\rm str}\approx1.13$, matching the recovery thresholds established for spectrally initialized AMP. The key technical ingredients are twofold: (i) a non-asymptotic coupling that decomposes the AMP iterates as a signal component, a linear combination of independent Gaussian vectors, and an approximation error, and (ii) a second-order analysis of the Onsager correction error built around a non-asymptotic version of Bolthausen's condition. These allow us to analyze the $O_δ(\log n)$ steps required for weak recovery, and to faithfully track the asymptotic state evolution up to $n^{1/3}/\operatorname{polylog}(n)$ steps in the intermediate recovery regime $δ\in(δ_{\rm weak},δ_{\rm str})$, both beyond the $O(1)$-iteration horizon of classical AMP theory. Above the strong recovery threshold, AMP reaches any prescribed fixed recovery accuracy within $O_{δ,\varepsilon}(\log n)$ iterations. Both the coupling and the error analysis are developed for a broad class of generalized AMP dynamics and may be of independent interest for general single-index models.
- fields
- Statistics Theory