Phase Retrieval via Wirtinger Flow: Theory and Algorithms

By E.J. Candes, Xiaodong Li, M. Soltanolkotabi. 2014

1,398 citations recorded by the source corpus.

We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal x ∈ ℂn about which we have phaseless samples of the form yr = |〈ar, x〉|2, r = 1, ..., m (knowledge of the phase of these samples would yield a linear system). This paper develops a nonconvex formulation of the phase retrieval problem as well as a concrete solution algorithm. In a nutshell, this algorithm starts with a careful initialization obtained by means of a spectral method, and then refines this initial estimate by iteratively applying novel update rules, which have low computational complexity, much like in a gradient descent scheme. The main contribution is that this algorithm is shown to rigorously allow the exact retrieval of phase information from a nearly minimal number of random measurements. Indeed, the sequence of successive iterates provably converges to the solution at a geometric rate so that the proposed scheme is efficient both in terms of computational and data resources. In theory, a variation on this scheme leads to a near-linear time algorithm for a physically realizable model based on coded diffraction patterns. We illustrate the effectiveness of our methods with various experiments on image data. Underlying our analysis are insights for the analysis of nonconvex optimization schemes that may have implications for computational problems beyond phase retrieval.

Subfields: Computer Vision and Pattern Recognition, Radiation, Structural Biology, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Dacheng Tao
  3. Ming-Hsuan Yang
  4. Trevor Darrell
  5. Xiaogang Wang
  6. Yi Yang
  7. Jitendra Malik
  8. Andrew Zisserman

In Radiation

  1. Yuxin Chen
  2. Tom Goldstein
  3. Christoph Studer
  4. Yuejie Chi
  5. E.J. Candes
  6. Yonina C. Eldar
  7. Prateek Jain
  8. M. Soltanolkotabi

In Structural Biology

  1. Yuxin Chen
  2. Yuejie Chi
  3. Christoph Studer
  4. Tom Goldstein
  5. Ganzhao Yuan
  6. Bernard Ghanem
  7. Sujay Sanghavi
  8. Prateek Jain

In Optimization & Training

  1. Jason D. Lee
  2. Michael I. Jordan
  3. Yuejie Chi
  4. Yuxin Chen
  5. Praneeth Netrapalli
  6. Yonina C. Eldar
  7. Peter L. Bartlett
  8. Yue M. Lu

Citations in the corpus