Phase retrieval using coordinate descent techniques

Abstract

Coordinate descent is applied to recover a signal-of-interest from only magnitude information. In doing so, a single unknown value is solved at each iteration, while all other variables are held constant. As a result, only minimization of a univariate quartic polynomial is required, which is efficiently achieved by finding the closed-form roots of a cubic polynomial. Cyclic, randomized, and/or a greedy coordinate descent technique can be used. Each coordinate descent technique globally converges to a stationary point of the nonconvex problem, and specifically, the randomized coordinate descent technique locally converges to the global minimum and attains exact recovery of the signal-of-interest at a geometric rate with high probability when the sample size is sufficiently large. The cyclic and randomized coordinate descent techniques can also be modified via minimization of the l-regularized quartic polynomial for phase retrieval of sparse signals-of-interest, i.e., those signals with only a few nonzero elements.