Wirtinger Flow

swMATH ID: 34175
Software Authors: Emmanuel Candes, Xiaodong Li, Mahdi Soltanolkotabi
Description: 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.
Homepage: https://arxiv.org/abs/1407.1065
Related Software: PhaseLift; PhaseMax; GESPAR; SparsePR; CVX; PhaseCut; PhasePack; CoSaMP; SDPLR; ADMiRA; MCPLIB; TFOCS; Cross; LMaFit; Manopt; BlockPR; BranchHull; TensorFlow; Complex Optimization Toolbox; AlexNet
Cited in: 136 Publications
all top 5

Cited by 279 Authors

9 Cai, Jian-Feng
7 Wang, Yang
5 Chi, Yuejie
5 Wei, Ke
4 Bahmani, Sohail
4 Bala Abubakar, Auwal
4 Chen, Pengwen
4 Chen, Yuxin
4 Huang, Meng
4 Ibrahim, Abdulkarim Hassan
4 Iwen, Mark A.
4 Li, Huiping
4 Li, Song
4 Ma, Cong
4 Wang, Hongxia
3 Davis, Damek
3 Drusvyatskiy, Dmitriy
3 Fan, Jianqing
3 Fannjiang, Albert C.
3 Guo, Yukun
3 Krahmer, Felix
3 Kueng, Richard
3 Li, Dong
3 Li, Ji
3 Ling, Shuyang
3 Lou, Yifei
3 Stöger, Dominik
3 Sun, Qiyu
3 Zeng, Tie Yong
3 Zhang, Deyue
2 Alaifari, Rima
2 Bendory, Tamir
2 Candès, Emmanuel J.
2 Chan, Tony Fan-Cheong
2 Chang, Huibin
2 Charisopoulos, Vasileios
2 Cheng, Cheng
2 Duchi, John C.
2 Edidin, Dan
2 Eldar, Yonina Chana
2 Gao, Bing
2 Hand, Paul E.
2 Jung, Peter
2 Kumam, Poom
2 Lavaei, Javad
2 Leung, Shingyu
2 Li, Jingzhi
2 Liu, Gi-Ren
2 Liu, Haixia
2 Lu, Yue M.
2 Marchesini, Stefano
2 Mondelli, Marco
2 Muangchoo, Kanikar
2 Neykov, Matey
2 Rano, Sadiya Ali
2 Rauhut, Holger
2 Romberg, Justin K.
2 Saab, Rayan
2 Sabach, Shoham
2 Sojoudi, Somayeh
2 Strohmer, Thomas
2 Sun, Ju
2 Terstiege, Ulrich
2 Viswanathan, Aditya
2 Wang, Kaizheng
2 Wang, Zhaoran
2 Wen, Zaiwen
2 Xu, Zhiqiang
2 Yazici, Birsen
2 Yonel, Bariscan
2 Yuan, Ziyang
2 Zhang, Anru R.
2 Zhang, Bo
2 Zhang, Haiwen
2 Zhao, Hongkai
1 Abbe, Emmanuel
1 Abubakar, Jamilu
1 Aghasi, Alireza
1 Ahookhosh, Masoud
1 Aremu, Kazeem Olalekan
1 Arguello, Henry
1 Augustin, Sven
1 Aviles-Rivero, Angelica I.
1 Balan, Radu V.
1 Bandegi, Mahdi
1 Barmherzig, David A.
1 Ben Arous, Gérard
1 Benson, Austin R.
1 Bolte, Jérôme
1 Bossmann, Florian
1 Brooks, Dana H.
1 Burger, Martin
1 Cai, Changxiao
1 Carlsson, Marcus
1 Carmon, Yair
1 Chaipunya, Parin
1 Chen, Ji
1 Chen, Yudong
1 Cheng, Chi-yu
1 Cui, Ying
...and 179 more Authors
all top 5

Cited in 49 Serials

14 Applied and Computational Harmonic Analysis
9 Inverse Problems
9 Journal of Machine Learning Research (JMLR)
8 Mathematical Programming. Series A. Series B
8 SIAM Journal on Optimization
7 Foundations of Computational Mathematics
5 The Journal of Fourier Analysis and Applications
5 SIAM Journal on Imaging Sciences
4 SIAM Journal on Matrix Analysis and Applications
4 SIAM Journal on Mathematics of Data Science
3 The Annals of Statistics
3 Journal of Computational and Applied Mathematics
3 Advances in Computational Mathematics
3 Inverse Problems and Imaging
3 Electronic Journal of Statistics
2 Journal of Optimization Theory and Applications
2 Mathematics and Computers in Simulation
2 Advances in Applied Mathematics
2 Journal of Scientific Computing
2 Computational Optimization and Applications
2 SIAM Journal on Scientific Computing
2 Journal of Statistical Mechanics: Theory and Experiment
2 Inverse Problems in Science and Engineering
2 Information and Inference
2 Annals of Applied Mathematics
2 Sampling Theory, Signal Processing, and Data Analysis
1 IEEE Transactions on Information Theory
1 Journal of the Franklin Institute
1 Automatica
1 Mathematics of Operations Research
1 Numerical Functional Analysis and Optimization
1 Operations Research
1 Results in Mathematics
1 Mathematica Numerica Sinica
1 Acta Applicandae Mathematicae
1 Japan Journal of Industrial and Applied Mathematics
1 Linear Algebra and its Applications
1 SIAM Journal on Applied Mathematics
1 Applied Mathematics. Series B (English Edition)
1 Bernoulli
1 Mathematical Problems in Engineering
1 SIAM Journal on Applied Dynamical Systems
1 Communications in Mathematical Sciences
1 Analysis and Applications (Singapore)
1 Optimization Letters
1 Arabian Journal of Mathematics
1 Journal of Mathematics
1 Electronic Research Archive
1 Fixed Point Theory and Algorithms for Sciences and Engineering

Citations by Year