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; CoSaMP; ADMiRA; PhasePack; SDPLR; TFOCS; MCPLIB; Cross; LMaFit; Manopt; BlockPR; BranchHull; minpack; ElemStatLearn; iPiano
Referenced in: 120 Publications
all top 5

Referenced by 232 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 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 Iwen, Mark A.
3 Li, Ji
3 Ling, Shuyang
3 Lou, Yifei
3 Sun, Qiyu
3 Zeng, Tie Yong
3 Zhang, Deyue
2 Alaifari, Rima
2 Candès, Emmanuel J.
2 Chan, Tony Fan-Cheong
2 Chang, Huibin
2 Charisopoulos, Vasileios
2 Cheng, Cheng
2 Duchi, John C.
2 Eldar, Yonina Chana
2 Gao, Bing
2 Hand, Paul E.
2 Krahmer, Felix
2 Kueng, Richard
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 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 Stöger, Dominik
2 Strohmer, Thomas
2 Sun, Ju
2 Terstiege, Ulrich
2 Viswanathan, Aditya
2 Wang, Kaizheng
2 Wang, Zhaoran
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 Aremu, Kazeem Olalekan
1 Arguello, Henry
1 Augustin, Sven
1 Bandegi, Mahdi
1 Barmherzig, David A.
1 Ben Arous, Gérard
1 Bendory, Tamir
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 Damle, Anil
1 d’Aspremont, Alexandre
1 Daubechies, Ingrid Chantal
1 Di, Zichao
1 Díaz, Mateo
1 Ding, Lijun
1 Dragomir, Radu-Alexandru
1 Edidin, Dan
1 Elser, Veit
1 Fadugba, Sunday Emmanuel
...and 132 more Authors
all top 5

Referenced in 44 Serials

14 Applied and Computational Harmonic Analysis
9 Inverse Problems
7 Mathematical Programming. Series A. Series B
7 Journal of Machine Learning Research (JMLR)
6 SIAM Journal on Optimization
6 Foundations of Computational Mathematics
5 SIAM Journal on Imaging Sciences
4 The Journal of Fourier Analysis and Applications
4 SIAM Journal on Mathematics of Data Science
3 The Annals of Statistics
3 Journal of Computational and Applied Mathematics
3 SIAM Journal on Matrix Analysis and Applications
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 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
1 IEEE Transactions on Information Theory
1 Journal of the Franklin Institute
1 Automatica
1 Operations Research
1 Results in Mathematics
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

Referencing Publications by Year