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.
Keywords for this software
References in zbMATH (referenced in 90 articles , 1 standard article )
Showing results 1 to 20 of 90.
Sorted by year (- 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)
- Alaifari, Rima; Wellershoff, Matthias: Stability estimates for phase retrieval from discrete Gabor measurements (2021)
- Arous, Gerard Ben; Gheissari, Reza; Jagannath, Aukosh: Online stochastic gradient descent on non-convex losses from high-dimensional inference (2021)
- Cheng, Cheng; Sun, Qiyu: Stable phaseless sampling and reconstruction of real-valued signals with finite rate of innovation (2021)
- Dragomir, Radu-Alexandru; d’Aspremont, Alexandre; Bolte, Jérôme: Quartic first-order methods for low-rank minimization (2021)
- Gao, Bing; Liu, Haixia; Wang, Yang: Phase retrieval for sub-Gaussian measurements (2021)
- Li, Ji; Cai, Jian-Feng; Zhao, Hongkai: Scalable incremental nonconvex optimization approach for phase retrieval (2021)
- Na, Sen; Kolar, Mladen: High-dimensional index volatility models via Stein’s identity (2021)
- Zhang, Deyue; Guo, Yukun: Some recent developments in the unique determinations in phaseless inverse acoustic scattering theory (2021)
- Abbe, Emmanuel; Fan, Jianqing; Wang, Kaizheng; Zhong, Yiqiao: Entrywise eigenvector analysis of random matrices with low expected rank (2020)
- Aghasi, Alireza; Ahmed, Ali; Hand, Paul; Joshi, Babhru: BranchHull: convex bilinear inversion from the entrywise product of signals with known signs (2020)
- Bendory, Tamir; Edidin, Dan; Eldar, Yonina C.: On signal reconstruction from FROG measurements (2020)
- Carlsson, Marcus; Gerosa, Daniele: On phase retrieval via matrix completion and the estimation of low rank PSD matrices (2020)
- Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron: Lower bounds for finding stationary points I (2020)
- Chen, Yang; Cheng, Cheng; Sun, Qiyu; Wang, Haichao: Phase retrieval of real-valued signals in a shift-invariant space (2020)
- Eldar, Yonina C.; Liao, Wenjing; Tang, Sui: Sensor calibration for off-the-grid spectral estimation (2020)
- Fung, Samy Wu; Di, Zichao: Multigrid optimization for large-scale ptychographic phase retrieval (2020)
- Ha, Wooseok; Liu, Haoyang; Barber, Rina Foygel: An equivalence between critical points for rank constraints versus low-rank factorizations (2020)
- Iwen, Mark A.; Preskitt, Brian; Saab, Rayan; Viswanathan, Aditya: Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization (2020)
- Jaming, Philippe; Kellay, Karim; Perez, Rolando III: Phase retrieval for wide band signals (2020)