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 101 articles , 1 standard article )
Showing results 1 to 20 of 101.
Sorted by year (- Cai, Jian-Feng; Li, Jingzhi; Lu, Xiliang; You, Juntao: Sparse signal recovery from phaseless measurements via hard thresholding pursuit (2022)
- Abubakar, Auwal Bala; Kumam, Poom; Mohammad, Hassan; Ibrahim, Abdulkarim Hassan: PRP-like algorithm for monotone operator equations (2021)
- 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)
- 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)
- Bahmani, Sohail; Lee, Kiryung: Low-rank matrix estimation from rank-one projections by unlifted convex optimization (2021)
- Charisopoulos, Vasileios; Benson, Austin R.; Damle, Anil: Communication-efficient distributed eigenspace estimation (2021)
- Cheng, Cheng; Sun, Qiyu: Stable phaseless sampling and reconstruction of real-valued signals with finite rate of innovation (2021)
- Chen, Yuxin; Fan, Jianqing; Ma, Cong; Yan, Yuling: Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data (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)
- Huang, Meng; Xu, Zhiqiang: Phase retrieval from the norms of affine transformations (2021)
- Li, Huiping; Li, Song: Phase retrieval from Fourier measurements with masks (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)
- Tong, Tian; Ma, Cong; Chi, Yuejie: Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent (2021)
- Xia, Dong: Normal approximation and confidence region of singular subspaces (2021)
- Xiao, Zhuolei; Wang, Ya; Gui, Guan: Smoothed amplitude flow-based phase retrieval algorithm (2021)
- Zhang, Deyue; Guo, Yukun: Some recent developments in the unique determinations in phaseless inverse acoustic scattering theory (2021)