Truncated Wirtinger Flow and Truncated Spectral Initialization for Random Quadratic Systems

An adaptive nonconvex phase-retrieval and quadratic-sensing algorithm (introduced by Yuxin Chen and Emmanuel J. Candès in 2017) that solves $m$ random quadratic equations $y_i = |\boldsymbol{a}_i^*\boldsymbol{x}|^2$ (or noisy Poisson intensity observations $y_i \sim \mathrm{Poisson}(|\boldsymbol{a}_i^*\boldsymbol{x}|^2)$) in $O(m n \log(1/\epsilon))$ total flops from an information-theoretically optimal sample size $m \asymp n$. Rather than minimizing the heavy-tailed quartic intensity residual, Truncated Wirtinger Flow (TWF, Algorithm 1) maximizes the Poisson log-likelihood $\sum_{i=1}^m [y_i\log(|\boldsymbol{a}_i^*\boldsymbol{z}|^2) - |\boldsymbol{a}_i^*\boldsymbol{z}|^2]$ using two statistically adaptive truncation mechanisms: (1) *Truncated Spectral Initialization* (Equations 2.6–2.7), which computes the leading eigenvector of $\boldsymbol{Y} = \frac{1}{m}\sum_{i=1}^m y_i\boldsymbol{a}_i\boldsymbol{a}_i^*\mathbb{I}_{\{|y_i| \le \alpha_y^2 (\frac{1}{m}\sum_l y_l)\}}$ discarding measurements where $|y_i|$ exceeds $\alpha_y^2\|\boldsymbol{x}\|^2$ so that the summands are bounded and concentrate at $m \asymp n$ via matrix Bernstein; and (2) *Truncated Wirtinger Gradient Updates* $\boldsymbol{z}^{(t+1)} = \boldsymbol{z}^{(t)} + \frac{\mu_t}{m}\sum_{i\in\mathcal{E}_1^{(t)}\cap\mathcal{E}_2^{(t)}} \frac{y_i - |\boldsymbol{a}_i^*\boldsymbol{z}^{(t)}|^2}{\boldsymbol{z}^{(t)*}\boldsymbol{a}_i}\boldsymbol{a}_i$ (Equations 2.4–2.5, 2.8–2.10), where $\mathcal{E}_1^{(t)} = \{\alpha_z^{\mathrm{lb}} \le \frac{|\boldsymbol{a}_i^*\boldsymbol{z}^{(t)}|}{\|\boldsymbol{z}^{(t)}\|} \le \alpha_z^{\mathrm{ub}}\}$ prevents division by small inner products $|\boldsymbol{a}_i^*\boldsymbol{z}^{(t)}|$ and $\mathcal{E}_2^{(t)} = \{|y_i - |\boldsymbol{a}_i^*\boldsymbol{z}^{(t)}|^2| \le \alpha_h K_t \frac{|\boldsymbol{a}_i^*\boldsymbol{z}^{(t)}|}{\|\boldsymbol{z}^{(t)}\|}\}$ (with empirical median residual $K_t = \mathrm{median}_i(|y_i - |\boldsymbol{a}_i^*\boldsymbol{z}^{(t)}|^2|)$) suppresses high-leverage residual outliers. Theorems 1–2 prove linear convergence $\mathrm{dist}(\boldsymbol{z}^{(t)},\boldsymbol{x}) \le \delta_0(1-\rho)^t\|\boldsymbol{x}\|$ with constant step size $\mu_t = \mu_0 \asymp 1$ and minimax-optimal noise stability $\mathrm{dist}(\boldsymbol{z}^{(t)},\boldsymbol{x}) \lesssim \frac{\|\boldsymbol{\eta}\|_2}{\sqrt{m}\|\boldsymbol{x}\|}$.