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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Phase retrieval via Wirtinger flow: theory and algorithms. Zbl 1359.94069Candès, Emmanuel J.; Li, Xiaodong; Soltanolkotabi, Mahdi 2015 all top 5 Cited by 278 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, 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 1 Damle, Anil ...and 178 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 all top 5 Cited in 28 Fields 69 Operations research, mathematical programming (90-XX) 58 Information and communication theory, circuits (94-XX) 46 Numerical analysis (65-XX) 23 Statistics (62-XX) 19 Harmonic analysis on Euclidean spaces (42-XX) 16 Calculus of variations and optimal control; optimization (49-XX) 15 Computer science (68-XX) 14 Optics, electromagnetic theory (78-XX) 12 Linear and multilinear algebra; matrix theory (15-XX) 6 Functional analysis (46-XX) 5 Partial differential equations (35-XX) 5 Operator theory (47-XX) 5 Systems theory; control (93-XX) 4 Probability theory and stochastic processes (60-XX) 3 Combinatorics (05-XX) 3 Functions of a complex variable (30-XX) 2 Potential theory (31-XX) 2 Approximations and expansions (41-XX) 2 Integral equations (45-XX) 2 Differential geometry (53-XX) 2 Mechanics of deformable solids (74-XX) 1 Real functions (26-XX) 1 Convex and discrete geometry (52-XX) 1 General topology (54-XX) 1 Fluid mechanics (76-XX) 1 Quantum theory (81-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Astronomy and astrophysics (85-XX) Citations by Year