Wirtinger Flow Phase Retrieval and Spectral Initialization

A two-stage nonconvex optimization algorithm (introduced by Emmanuel J. Candès, Xiaodong Li, and Mahdi Soltanolkotabi in 2015) for recovering a complex or real signal $\boldsymbol{x} \in \mathbb{C}^n$ (up to a global unimodular phase factor $e^{i\phi}$) from $m$ phaseless quadratic intensity measurements $y_r = |\langle \boldsymbol{a}_r, \boldsymbol{x}\rangle|^2$, $r = 1,\dots,m$. Stage 1 (*Spectral Initialization*, Algorithm 1) computes the leading eigenvector of the weighted data covariance matrix $\boldsymbol{Y} = \frac{1}{m}\sum_{r=1}^m y_r\boldsymbol{a}_r\boldsymbol{a}_r^*$ (whose population expectation under Gaussian design is $\mathbb{E}[\boldsymbol{Y}] = \|\boldsymbol{x}\|^2\boldsymbol{I}_n + \boldsymbol{x}\boldsymbol{x}^*$) scaled to norm $\lambda_0 = \sqrt{n\sum_r y_r / \sum_r \|\boldsymbol{a}_r\|^2}$ to produce an initial iterate $\boldsymbol{z}_0$ satisfying $\mathrm{dist}(\boldsymbol{z}_0, \boldsymbol{x}) \le \frac{1}{8}\|\boldsymbol{x}\|$ (Section 7.1, Lemma 7.8). Stage 2 (*Wirtinger Flow*, Algorithm 1, Equation 2.2) minimizes the nonconvex quartic intensity loss $f(\boldsymbol{z}) = \frac{1}{2m}\sum_{r=1}^m (|\langle\boldsymbol{a}_r, \boldsymbol{z}\rangle|^2 - y_r)^2$ via complex Wirtinger-calculus gradient updates $\boldsymbol{z}_{\tau+1} = \boldsymbol{z}_\tau - \frac{\mu_{\tau+1}}{\|\boldsymbol{z}_0\|^2}\frac{1}{m}\sum_{r=1}^m (|\langle\boldsymbol{a}_r,\boldsymbol{z}_\tau\rangle|^2 - y_r)(\boldsymbol{a}_r\boldsymbol{a}_r^*)\boldsymbol{z}_\tau$. By establishing a local *Regularity Condition* $\mathrm{Re}(\langle\nabla f(\boldsymbol{z}), \boldsymbol{z} - \boldsymbol{x}e^{i\phi(\boldsymbol{z})}\rangle) \ge \frac{1}{\alpha}\mathrm{dist}^2(\boldsymbol{z},\boldsymbol{x}) + \frac{1}{\beta}\|\nabla f(\boldsymbol{z})\|^2$ in the basin $E(\boldsymbol{x}) = \{\boldsymbol{z} : \mathrm{dist}(\boldsymbol{z},\boldsymbol{x}) \le \frac{1}{8}\|\boldsymbol{x}\|\}$ via shared local smoothness and curvature bounds (Condition 7.9, Lemmas 7.2–7.7), Theorem 3.3 proves exact geometric convergence $\mathrm{dist}(\boldsymbol{z}_\tau, \boldsymbol{x}) \le \frac{1}{8}(1 - \frac{2\mu}{\alpha})^{\tau/2}\|\boldsymbol{x}\|$ from $m \ge c_0 n\log n$ Gaussian measurements or $L \ge c_1\log^4 n$ coded diffraction patterns (CDPs) with admissible fourth-moment modulation $\mathbb{E}[|d|^4] = 2(\mathbb{E}[|d|^2])^2$ (Equation 2.3).