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 δ∈(δ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.