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 41 to 60 of 110.
Sorted by year (citations)
  1. Li, Ji; Zhao, Hongkai: Solving phase retrieval via graph projection splitting (2020)
  2. Ma, Cong; Wang, Kaizheng; Chi, Yuejie; Chen, Yuxin: Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution (2020)
  3. Ma, Zhuang; Ma, Zongming; Yuan, Hongsong: Universal latent space model fitting for large networks with edge covariates (2020)
  4. Mukkamala, Mahesh Chandra; Ochs, Peter; Pock, Thomas; Sabach, Shoham: Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization (2020)
  5. Neykov, Matey; Wang, Zhaoran; Liu, Han: Agnostic estimation for phase retrieval (2020)
  6. Pang, Tongyao; Li, Qingna; Wen, Zaiwen; Shen, Zuowei: Phase retrieval: a data-driven wavelet frame based approach (2020)
  7. Saglietti, Luca; Lu, Yue M.; Lucibello, Carlo: Generalized approximate survey propagation for high-dimensional estimation (2020)
  8. Sissouno, Nada; Boßmann, Florian; Filbir, Frank; Iwen, Mark; Kahnt, Maik; Saab, Rayan; Schroer, Christian; zu Castell, Wolfgang: A direct solver for the phase retrieval problem in ptychographic imaging (2020)
  9. Wei, Ke; Cai, Jian-Feng; Chan, Tony F.; Leung, Shingyu: Guarantees of Riemannian optimization for low rank matrix completion (2020)
  10. Wong, Wing Hong; Lou, Yifei; Marchesini, Stefano; Zeng, Tieyong: One-dimensional phase retrieval: regularization, box relaxation and uniqueness (2020)
  11. Xiong, Huaqing; Chi, Yuejie; Hu, Bin; Zhang, Wei: Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition (2020)
  12. Zhang, Anru R.; Luo, Yuetian; Raskutti, Garvesh; Yuan, Ming: ISLET: Fast and optimal low-rank tensor regression via importance sketching (2020)
  13. Zhang, Deyue; Guo, Yukun; Sun, Fenglin; Liu, Hongyu: Unique determinations in inverse scattering problems with phaseless near-field measurements (2020)
  14. Zhang, Deyue; Wang, Yinglin; Guo, Yukun; Li, Jingzhi: Uniqueness in inverse cavity scattering problems with phaseless near-field data (2020)
  15. Zhang, Teng: Phase retrieval using alternating minimization in a batch setting (2020)
  16. Zhou, Zhiyong; Yu, Jun: Phaseless compressive sensing using partial support information (2020)
  17. Alaifari, Rima; Daubechies, Ingrid; Grohs, Philipp; Yin, Rujie: Stable phase retrieval in infinite dimensions (2019)
  18. Bahmani, Sohail: Estimation from nonlinear observations via convex programming with application to bilinear regression (2019)
  19. Bahmani, Sohail; Romberg, Justin: Solving equations of random convex functions via anchored regression (2019)
  20. Barmherzig, David A.; Sun, Ju; Li, Po-Nan; Lane, T. J.; Candès, Emmanuel J.: Holographic phase retrieval and reference design (2019)