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 61 to 80 of 110.
Sorted by year (citations)
  1. Burger, Martin; Föcke, Janic; Nickel, Lukas; Jung, Peter; Augustin, Sven: Reconstruction methods in THz single-pixel imaging (2019)
  2. Cai, Jian-Feng; Liu, Haixia; Wang, Yang: Fast rank-one alternating minimization algorithm for phase retrieval (2019)
  3. Chen, Ji; Li, Xiaodong: Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA (2019)
  4. Chen, Yuxin; Chi, Yuejie; Fan, Jianqing; Ma, Cong: Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval (2019)
  5. Chi, Yuejie; Li, Yuanxin; Zhang, Huishuai; Liang, Yingbin: Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation (2019)
  6. Davis, Damek; Drusvyatskiy, Dmitriy: Stochastic model-based minimization of weakly convex functions (2019)
  7. Geppert, Jakob; Krahmer, Felix; Stöger, Dominik: Sparse power factorization: balancing peakiness and sample complexity (2019)
  8. Hand, Paul; Voroninski, Vladislav: An elementary proof of convex phase retrieval in the natural parameter space via the linear program PhaseMax (2019)
  9. Lee, Jason D.; Panageas, Ioannis; Piliouras, Georgios; Simchowitz, Max; Jordan, Michael I.; Recht, Benjamin: First-order methods almost always avoid strict saddle points (2019)
  10. Liu, Huikang; So, Anthony Man-Cho; Wu, Weijie: Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods (2019)
  11. Li, Xiaodong; Ling, Shuyang; Strohmer, Thomas; Wei, Ke: Rapid, robust, and reliable blind deconvolution via nonconvex optimization (2019)
  12. Luke, D. Russell; Sabach, Shoham; Teboulle, Marc: Optimization on spheres: models and proximal algorithms with computational performance comparisons (2019)
  13. Mondelli, Marco; Montanari, Andrea: Fundamental limits of weak recovery with applications to phase retrieval (2019)
  14. Roig-Solvas, Biel; Makowski, Lee; Brooks, Dana H.: A proximal operator for multispectral phase retrieval problems (2019)
  15. Wang, Chuang; Lu, Yue M.: The scaling limit of high-dimensional online independent component analysis (2019)
  16. Yang, Zhuoran; Yang, Lin F.; Fang, Ethan X.; Zhao, Tuo; Wang, Zhaoran; Neykov, Matey: Misspecified nonconvex statistical optimization for sparse phase retrieval (2019)
  17. Yonel, Bariscan; Yazici, Birsen: A generalization of Wirtinger flow for exact interferometric inversion (2019)
  18. Yuan, Ziyang; Wang, Hongxia; Wang, Qi: Phase retrieval via sparse Wirtinger flow (2019)
  19. Zhang, Richard Y.; Sojoudi, Somayeh; Lavaei, Javad: Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery (2019)
  20. Bandegi, Mahdi; Shirokoff, David: Approximate global minimizers to pairwise interaction problems via convex relaxation (2018)