Randomly Initialized Gradient Descent and Leave-One-Out Sign-Flip Phase Retrieval Analysis

The global convergence theory and two-stage trajectory analysis of vanilla Wirtinger Flow gradient descent $x^{t+1} = x^t - \eta_t \nabla f(x^t)$ on the nonconvex fourth-order intensity loss $f(x) = \frac{1}{4m}\sum_{i=1}^m ((a_i^\top x)^2 - y_i)^2$ from a *random initialization* $x^0$ without spectral initialization, truncation, or sample splitting, established by Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma (2019). Decomposing $x^t$ into signal strength $\alpha_t = x_1^t$ (aligned with $x^\natural = e_1$) and orthogonal component $\beta_t = \|x_{2:n}^t\|_2$, the approximate state evolution $\alpha_{t+1} \approx [1 + 3\eta(1 - (\alpha_t^2+\beta_t^2))]\alpha_t$ and $\beta_{t+1} \approx [1 + \eta(1 - 3(\alpha_t^2+\beta_t^2))]\beta_t$ (Equations 9a–9b) satisfies $\frac{\alpha_{t+1}/\alpha_t}{\beta_{t+1}/\beta_t} = 1 + \frac{2\eta}{1 + \eta(1 - 3(\|x^t\|_2^2))} > 1$, driving exponential growth of the signal-to-noise ratio $\alpha_t/\beta_t$ from $\Theta(1/\sqrt{n\log n})$ to $\Omega(1)$ in $T_0 = O(\log n)$ steps (Stage 1 saddle-escaping phase, Lemma 1) followed by geometric contraction $\mathrm{dist}(x^t, x^\natural) \le O((1-c\eta)^{t-T_0})$ in $O(\log(1/\varepsilon))$ additional steps (Stage 2, Lemma 2) whenever $m \gtrsim n\,\mathrm{poly}\log n$ (Theorems 1 and 3). To control statistical dependence between $x^t$ and $a_i$ during Stage 1 where $|x_1^t| \asymp 1/\sqrt{n}$ is as small as the leave-one-out perturbation, the proof introduces coupled *leave-one-out* ($x^{t,(l)}$), *random-sign* ($x^{t,\mathrm{sgn}}$ with $a_{i,1}^{\mathrm{sgn}} = \xi_i^{\mathrm{sgn}}|a_{i,1}|$), and *leave-one-out random-sign* ($x^{t,\mathrm{sgn},(l)}$) auxiliary trajectories (Algorithms 1–3, Lemmas 4–7).