PhaseLiftOff: An accurate and stable phase retrieval method based on difference of trace and Frobenius norms

Phase retrieval aims to recover a signal $x \in \mathbb{C}^n$ from its amplitude measurements ${\vert \langle x, a_i \rangle \rvert}^2 , i=1, 2, \cdots , m, \;$ where $a_i$’s are over-complete basis vectors, with $m$ at least $3n - 2$ to ensure a unique solution up to a constant phase factor. The quadratic measurement becomes linear in terms of the rank-one matrix $X = xx^*$. Phase retrieval is then a rank-one minimization problem subject to linear constraint for which a convex relaxation based on trace-norm minimization (PhaseLift) has been extensively studied recently. At $m=O(n)$, PhaseLift recovers with high probability the rank-one solution. In this paper, we present a precise proxy of the rank-one condition via the difference of trace and Frobenius norms which we call PhaseLiftOff. The associated least squares minimization with this penalty as regularization is equivalent to the rank-one least squares problem under a mild condition on the measurement noise. Stable recovery error estimates are valid at $m=O(n)$ with high probability. Computation of PhaseLiftOff minimization is carried out by a convergent difference of convex functions algorithm. In our numerical example, $a_i$’s are Gaussian distributed. Numerical results show that PhaseLiftOff outperforms PhaseLift and its nonconvex variant (log-determinant regularization), and successfully recovers signals near the theoretical lower limit on the number of measurements without the noise.

Keywords

phase retrieval, phase lift regularized by trace minus Frobenius norms, equivalent minimization problems, Karush-Kuhn-Tucker conditions, difference of convex functions algorithm, convergence

2010 Mathematics Subject Classification

65K05, 90C22, 94A12

Full Text (PDF format)

Published 12 March 2015