Approximate Message Passing with Random Initialization for Phase Retrieval

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.