Wirtinger Flow

Phase Retrieval via Wirtinger Flow: Theory and Algorithms. We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal x of C^n about which we have phaseless samples of the form y_r = |< a_r,x >|^2, r = 1,2,...,m (knowledge of the phase of these samples would yield a linear system). This paper develops a non-convex 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 non-convex optimization schemes that may have implications for computational problems beyond phase retrieval.


References in zbMATH (referenced in 110 articles , 1 standard article )

Showing results 81 to 100 of 110.
Sorted by year (citations)
  1. Cai, Jian-Feng; Wang, Tianming; Wei, Ke: Spectral compressed sensing via projected gradient descent (2018)
  2. Chang, Huibin; Marchesini, Stefano; Lou, Yifei; Zeng, Tieyong: Variational phase retrieval with globally convergent preconditioned proximal algorithm (2018)
  3. Chen, Pengwen; Fannjiang, Albert: Fourier phase retrieval with a single mask by Douglas-Rachford algorithms (2018)
  4. Chen, Pengwen; Fannjiang, Albert; Liu, Gi-Ren: Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization (2018)
  5. Davis, Damek; Drusvyatskiy, Dmitriy; MacPhee, Kellie J.; Paquette, Courtney: Subgradient methods for sharp weakly convex functions (2018)
  6. Duchi, John C.; Ruan, Feng: Stochastic methods for composite and weakly convex optimization problems (2018)
  7. Gao, Bing; Sun, Qiyu; Wang, Yang; Xu, Zhiqiang: Phase retrieval from the magnitudes of affine linear measurements (2018)
  8. Kech, Michael: Explicit frames for deterministic phase retrieval via PhaseLift (2018)
  9. Kümmerle, Christian; Sigl, Juliane: Harmonic mean iteratively reweighted least squares for low-rank matrix recovery (2018)
  10. Li, Ji; Zhou, Tie; Wang, Chao: On global convergence of gradient descent algorithms for generalized phase retrieval problem (2018)
  11. Lv, Fusheng; Sun, Wenchang: Real phase retrieval from unordered partial frame coefficients (2018)
  12. Pinilla, Samuel; García, Hans; Díaz, Luis; Poveda, Juan; Arguello, Henry: Coded aperture design for solving the phase retrieval problem in X-ray crystallography (2018)
  13. Sun, Ju; Qu, Qing; Wright, John: A geometric analysis of phase retrieval (2018)
  14. Xu, Xiaoxu; Zhang, Bo; Zhang, Haiwen: Uniqueness in inverse scattering problems with phaseless far-field data at a fixed frequency (2018)
  15. Yuan, Ziyang; Wang, Hongxia: Phase retrieval for sparse binary signal: uniqueness and algorithm (2018)
  16. Zhang, Bo; Zhang, Haiwen: Fast imaging of scattering obstacles from phaseless far-field measurements at a fixed frequency (2018)
  17. Chen, Pengwen; Fannjiang, Albert; Liu, Gi-Ren: Phase retrieval by linear algebra (2017)
  18. Kueng, Richard; Rauhut, Holger; Terstiege, Ulrich: Low rank matrix recovery from rank one measurements (2017)
  19. Sanghavi, Sujay; Ward, Rachel; White, Chris D.: The local convexity of solving systems of quadratic equations (2017)
  20. Bahmani, Sohail; Romberg, Justin: Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements (2016)