Coordinate descent algorithms for phase retrieval

Phase retrieval aims at recovering a complex-valued signal using the magnitude-only measurements of its linear transformation, and has wide applicability in areas including astronomy, computational biology, crystallography, digital communications, electron microscopy, neutron radiography and optical imaging. However, phase recovery involves solving a system of quadratic equations or minimizing a multivariate fourth-order polynomial, indicating that it is a challenging nonconvex optimization problem. To tackle phase retrieval in an effective and efficient manner, we apply coordinate descent (CD) such that a single unknown is solved at each iteration while all other variables are kept fixed. As a result, only minimization of a univariate quartic polynomial is needed which is easily achieved by finding the closed-form roots of a cubic equation. Three computationally simple algorithms referred to as cyclic, randomized and greedy CDs, based on different updating rules, are devised. It is proved that the three CDs globally converge to a stationary point of the nonconvex problem, and specifically, the randomized CD locally converges to the global minimum and attains exact recovery at a geometric rate with high probability if the sample size is large enough. The cyclic and randomized CDs are also modified via minimization of the ℓ₁-regularized quartic polynomial for phase retrieval of sparse signals. Furthermore, a novel application of the three CDs, namely, blind equalization in digital communications, is proposed. It is demonstrated that the CD methodology is superior to the state-of-the-art techniques in terms of computational efficiency and/or recovery performance.