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 1 to 20 of 110.
Sorted by year (citations)

1 2 3 4 5 6 next

  1. Cai, Jian-Feng; Huang, Meng; Li, Dong; Wang, Yang: Solving phase retrieval with random initial guess is nearly as good as by spectral initialization (2022)
  2. Cai, Jian-Feng; Li, Jingzhi; Lu, Xiliang; You, Juntao: Sparse signal recovery from phaseless measurements via hard thresholding pursuit (2022)
  3. Chen, Pengwen: Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval (2022)
  4. Han, Rungang; Willett, Rebecca; Zhang, Anru R.: An optimal statistical and computational framework for generalized tensor estimation (2022)
  5. Abubakar, Auwal Bala; Kumam, Poom; Mohammad, Hassan; Ibrahim, Abdulkarim Hassan: PRP-like algorithm for monotone operator equations (2021)
  6. Abubakar, Auwal Bala; Muangchoo, Kanikar; Ibrahim, Abdulkarim Hassan; Abubakar, Jamilu; Rano, Sadiya Ali: FR-type algorithm for finding approximate solutions to nonlinear monotone operator equations (2021)
  7. Abubakar, Auwal Bala; Muangchoo, Kanikar; Ibrahim, Abdulkarim Hassan; Fadugba, Sunday Emmanuel; Aremu, Kazeem Olalekan; Jolaoso, Lateef Olakunle: A modified scaled spectral-conjugate gradient-based algorithm for solving monotone operator equations (2021)
  8. Alaifari, Rima; Wellershoff, Matthias: Stability estimates for phase retrieval from discrete Gabor measurements (2021)
  9. Arous, Gerard Ben; Gheissari, Reza; Jagannath, Aukosh: Online stochastic gradient descent on non-convex losses from high-dimensional inference (2021)
  10. Bahmani, Sohail; Lee, Kiryung: Low-rank matrix estimation from rank-one projections by unlifted convex optimization (2021)
  11. Charisopoulos, Vasileios; Benson, Austin R.; Damle, Anil: Communication-efficient distributed eigenspace estimation (2021)
  12. Charisopoulos, Vasileios; Chen, Yudong; Davis, Damek; Díaz, Mateo; Ding, Lijun; Drusvyatskiy, Dmitriy: Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence (2021)
  13. Cheng, Cheng; Sun, Qiyu: Stable phaseless sampling and reconstruction of real-valued signals with finite rate of innovation (2021)
  14. Chen, Yuxin; Fan, Jianqing; Ma, Cong; Yan, Yuling: Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data (2021)
  15. Dragomir, Radu-Alexandru; d’Aspremont, Alexandre; Bolte, Jérôme: Quartic first-order methods for low-rank minimization (2021)
  16. Gao, Bing; Liu, Haixia; Wang, Yang: Phase retrieval for sub-Gaussian measurements (2021)
  17. Huang, Meng; Xu, Zhiqiang: Phase retrieval from the norms of affine transformations (2021)
  18. Li, Huiping; Li, Song: Riemannian optimization for phase retrieval from masked Fourier measurements (2021)
  19. Li, Huiping; Li, Song: Phase retrieval from Fourier measurements with masks (2021)
  20. Li, Ji; Cai, Jian-Feng; Zhao, Hongkai: Scalable incremental nonconvex optimization approach for phase retrieval (2021)

1 2 3 4 5 6 next