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 $\hat{I}{´}_{\mathrm{weak}}=1/2$. For $\hat{I}´\in (\hat{I}{´}_{\mathrm{weak}},\hat{I}{´}_{\mathrm{str}})$, where $\hat{I}{´}_{\mathrm{str}}\approx 1.13$, the signal strength follows state evolution and approaches its stable finite fixed point uniformly for \(n^{1/3}/\operatorname{polylog}(n)\) iterations. For $\hat{I}´>\hat{I}{´}_{\mathrm{str}}$, AMP reaches any prescribed fixed recovery accuracy within $O_{\hat{I}´,\epsilon }(\log n)$ iterations. The majority of our analysis applies more generally to generalized AMP for single-index models.