PhaseLift Convex Semidefinite Programming Matrix-Lifting for Phase Retrieval

A convex semidefinite programming (SDP) relaxation and dual-certificate recovery methodology (introduced by Emmanuel J. Candès, Thomas Strohmer, and Vladislav Voroninski in 2013) for reconstructing a real or complex signal $\boldsymbol{x}_0 \in \mathbb{R}^n$ or $\mathbb{C}^n$ (up to a global phase $e^{i\phi}$) from quadratic intensity measurements $b_k = |\langle \boldsymbol{a}_k, \boldsymbol{x}_0\rangle|^2 + w_k$ ($k=1,\dots,m$). By lifting the rank-1 outer product $\boldsymbol{X}_0 = \boldsymbol{x}_0\boldsymbol{x}_0^*$ into the positive semidefinite cone $\boldsymbol{X} \succeq \boldsymbol{0}$, the quadratic measurements become linear trace functionals $\mathcal{A}(\boldsymbol{X})_k = \mathrm{Tr}(\boldsymbol{a}_k\boldsymbol{a}_k^* \boldsymbol{X})$, and PhaseLift replaces combinatorial rank minimization with the trace-norm SDP $\min_{\boldsymbol{X}\succeq\boldsymbol{0}} \mathrm{Tr}(\boldsymbol{X})$ subject to $\mathcal{A}(\boldsymbol{X}) = \boldsymbol{b}$ in the noiseless case (Equation 1.8) or $\|\mathcal{A}(\boldsymbol{X}) - \boldsymbol{b}\|_1 \le \varepsilon$ in the noisy case (Equation 1.9). Using concentration of rank-2 $\ell_1$-isometry functionals $\frac{1}{m}\sum_{k=1}^m |\langle \boldsymbol{a}_k\boldsymbol{a}_k^*, \boldsymbol{H}\rangle|$ on the tangent space $T = \{\boldsymbol{x}_0\boldsymbol{y}^* + \boldsymbol{y}\boldsymbol{x}_0^*\}$ and its orthogonal complement $T^\perp$ (Lemmas 3.1–3.3) together with an inexact dual certificate $\boldsymbol{Y} = \mathcal{A}^*(\boldsymbol{\lambda})$ obeying $\|\boldsymbol{Y}_T\|_F \le 1/5$ and $\boldsymbol{Y}_{T^\perp} \preceq -c\boldsymbol{I}_{T^\perp}$ constructed from fourth-moment expectations $\mathcal{S}(\boldsymbol{X}) = \mathbb{E}[(\boldsymbol{z}^*\boldsymbol{X}\boldsymbol{z})\boldsymbol{z}\boldsymbol{z}^*] = \boldsymbol{X} + \mathrm{Tr}(\boldsymbol{X})\boldsymbol{I}$ (complex) or $2\boldsymbol{X} + \mathrm{Tr}(\boldsymbol{X})\boldsymbol{I}$ (real) (Section 3.2), Theorems 1.1 and 1.2 prove exact recovery $\widehat{\boldsymbol{X}} = \boldsymbol{x}_0\boldsymbol{x}_0^*$ and stable noisy recovery $\|\widehat{\boldsymbol{x}} - e^{i\phi}\boldsymbol{x}_0\|_2 \le C_0\min(\|\boldsymbol{x}_0\|_2, \frac{\varepsilon}{m\|\boldsymbol{x}_0\|_2})$ from $m \ge c_0 n\log n$ Gaussian or unitary-frame measurements without any initialization.