AltMinPhase and SparseAltMinPhase (Resampled Alternating Minimization for Phase Retrieval)

The first non-convex alternating minimization algorithm with provable global geometric convergence for phase retrieval and sparse phase retrieval (introduced by Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi in 2013/2015). Given magnitude measurements $y_i = |\langle a_i,x^*\rangle|$ ($i=1,\dots,m$), reformulating the measurement model with a diagonal unit-modulus phase matrix $C^* = \mathrm{diag}(\mathrm{Ph}(A x^*))$ yields $\min_{|C_{ii}|=1, x\in\mathbb{C}^n}\|A x - C y\|_2$ (Equation 1). *AltMinPhase* (Algorithm 1) initializes $x^0$ as the scaled leading eigenvector of the weighted covariance matrix $Y = \frac{1}{m}\sum_{\ell=1}^m y_\ell^2 a_\ell a_\ell^*$ (whose expectation $\mathbb{E}[Y] = \|x^*\|_2^2(I + 2\frac{x^*(x^*)^*}{\|x^*\|_2^2})$ has spectral gap 3 vs. 1), and at each iteration $t=0,\dots,T-1$ alternates between exact phase projection $C^{t+1} = \mathrm{diag}(\mathrm{Ph}(A^{(t+1)} x^t))$ and least-squares signal estimation $x^{t+1} = \arg\min_{x\in\mathbb{C}^n}\|A^{(t+1)} x - C^{t+1} y^{(t+1)}\|_2$ on a fresh sample batch $(A^{(t+1)},y^{(t+1)})$. By decomposing the true measurements as $y_i = c_i^*(a_i^\top x^*) = c_i^*(\alpha_t a_i^\top x^t - a_i^\top w^t)$ ($\langle x^t,w^t\rangle = 0$, $\|w^t\|_2 = \sqrt{1-\alpha_t^2}$), Lemma 4.3 proves that the phase-error vector $v_i^t = (c_i^t - c_i^*)y_i$ satisfies $\frac{1}{m}\|(A^{(t+1)})^* v^t\|_2 \le \frac{1}{2}\|w^t\|_2$ when $\mathrm{dist}(x^t,x^*) \le 1/6$, establishing per-step contraction $\mathrm{dist}(x^{t+1},x^*) \le \frac{3}{4}\mathrm{dist}(x^t,x^*)$ (Theorem 2.1) with $m = O(n\log^3 n(\log n + \log(1/\epsilon)))$ measurements. For $k$-sparse signals $x^*$, *SparseAltMinPhase* (Algorithm 2) selects support $\hat{S}$ from the top-$k$ marginal energy coordinates $\sum_{\ell=1}^m y_\ell^2 |a_{\ell j}|^2$ (whose gap separates $j\in S$ from $j\notin S$ whenever $|x_j^*| \ge \frac{C}{\sqrt{k}}\|x^*\|_2$, Lemma 5.1) or replaces least squares by CoSaMP, achieving $O((k^2\log n + k\log n\log(1/\epsilon)))$ sample complexity (Theorems 2.2–2.3).