Approximate Message Passing with Random Initialization for Phase Retrieval

Abstract

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 $δ\in(δ_{\rm weak},δ_{\rm str})$, where $δ_{\rm str}\approx1.13$, the signal strength follows state evolution and approaches its stable finite fixed point uniformly for \(n^{1/3}/\operatorname{polylog}(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.