Truncated Amplitude Flow and Orthogonality-Promoting Initialization for Random Quadratic Equations

A two-stage nonconvex-nonsmooth phase retrieval algorithm (introduced by Gang Wang, Georgios B. Giannakis, and Yonina C. Eldar in 2018) that recovers an unknown signal $\boldsymbol{x} \in \mathbb{R}^n$ or $\mathbb{C}^n$ from $m$ magnitude measurements $\psi_i = |\langle \boldsymbol{a}_i, \boldsymbol{x}\rangle|$ by minimizing the amplitude-based empirical loss $\ell(\boldsymbol{z}) = \frac{1}{2m}\sum_{i=1}^m (\psi_i - |\boldsymbol{a}_i^\top\boldsymbol{z}|)^2$ (Equation 5). Stage 1 introduces *orthogonality-promoting initialization* (Equations 14–23, Algorithm 1): exploiting the concentration of $\frac{1}{m}\sum_{i=1}^m \frac{\boldsymbol{a}_i\boldsymbol{a}_i^\top}{\|\boldsymbol{a}_i\|_2^2} \approx \frac{1}{n}\boldsymbol{I}_n$, it selects the subset $\overline{\mathcal{I}}_0$ of cardinality $|\overline{\mathcal{I}}_0| = \lceil \frac{1}{6}m\rceil$ corresponding to the largest normalized inner products $\psi_i / \|\boldsymbol{a}_i\|_2$, computes the leading unit eigenvector $\tilde{\boldsymbol{z}}_0$ of $\overline{\boldsymbol{Y}}_0 = \frac{1}{|\overline{\mathcal{I}}_0|}\sum_{i\in\overline{\mathcal{I}}_0} \frac{\boldsymbol{a}_i\boldsymbol{a}_i^\top}{\|\boldsymbol{a}_i\|_2^2}$ via power iterations without fourth-moment heavy tails, and scales $\boldsymbol{z}_0 = \sqrt{\frac{1}{m}\sum_{i=1}^m \psi_i^2}\,\tilde{\boldsymbol{z}}_0$. Stage 2 refines $\boldsymbol{z}_t$ via *truncated generalized gradient* iterations $\boldsymbol{z}_{t+1} = \boldsymbol{z}_t - \frac{\mu}{m}\sum_{i\in\mathcal{I}_{t+1}}(\boldsymbol{a}_i^\top\boldsymbol{z}_t - \psi_i \frac{\boldsymbol{a}_i^\top\boldsymbol{z}_t}{|\boldsymbol{a}_i^\top\boldsymbol{z}_t|})\boldsymbol{a}_i$ over the watershed truncation set $\mathcal{I}_{t+1} = \{1\le i\le m : |\boldsymbol{a}_i^\top\boldsymbol{z}_t| / \psi_i \ge \frac{1}{1+\gamma}\}$ (Equations 6–7 and 11), eliminating measurements near the hyperplane $\boldsymbol{a}_i^\top\boldsymbol{z}_t = 0$ whose estimated signs $\mathrm{sign}(\boldsymbol{a}_i^\top\boldsymbol{z}_t)$ disagree with $\mathrm{sign}(\boldsymbol{a}_i^\top\boldsymbol{x})$.