The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Open accessAbstract
We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal$ \boldsymbol {x}\in \mathbb {C}^{n}$about which we have phaseless samples of the form$y_{r} = \left |{\langle \boldsymbol {a}_{r}, \boldsymbol {x} \rangle }\right |^{2}$,$r = 1,\ldots , m$(knowledge of the phase of these samples would yield a linear system). This paper develops a nonconvex 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 nonconvex optimization schemes that may have implications for computational problems beyond phase retrieval.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Phase retrieval algorithms: a comparison
Fienup, J. R. (1982) · Applied Optics · doi:10.1364/ao.21.002758 · Cited by 5,596
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Message-passing algorithms for compressed sensing
Donoho, D. L., Maleki, A., & Montanari, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0909892106 · Cited by 2,416
Compressed sensing : theory and applications
Eldar, Y. C., & Gitta Kutyniok, B. (2012) · Cited by 2,028
Miao, J., Charalambous, P., Kirz, J., & Sayre, D. (1999) · Nature · doi:10.1038/22498 · Cited by 1,976
Reconstruction of an object from the modulus of its Fourier transform
Fienup, J. R. (1978) · Optics Letters · doi:10.1364/ol.3.000027 · Cited by 1,836
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Candès, E. J., Strohmer, T., & Voroninski, V. (2013) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21432 · Cited by 1,197
Self-citationGeneralized approximate message passing for estimation with random linear mixing
Rangan, S. (2011) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2011.6033942 · Cited by 1,103
Some NP-complete problems in quadratic and nonlinear programming
Murty, K. G., & Kabadi, S. N. (1987) · Mathematical Programming · doi:10.1007/bf02592948 · Cited by 1,003 · cited 1×
“We refer to the combination of these two steps, introduced in reverse order below, as the Wirtinger flow (WF) algorithm.”
MethodMatrix Completion From a Few Entries
Keshavan, R. H., Montanari, A., & Oh, S. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2046205 · Cited by 974
Low-rank matrix completion using alternating minimization
Jain, P., Netrapalli, P., & Sanghavi, S. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488693 · Cited by 817
The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
Bayati, M., & Montanari, A. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2094817 · Cited by 780
Phase retrieval in crystallography and optics
Millane, R. P. (1990) · Journal of the Optical Society of America A · doi:10.1364/josaa.7.000394 · Cited by 720
Multiplexed coded illumination for Fourier Ptychography with an LED array microscope
Tian, L., Li, X., Ramchandran, K., & Waller, L. (2014) · Biomedical Optics Express · doi:10.1364/boe.5.002376 · Cited by 584
Self-citationInvited Article: A unified evaluation of iterative projection algorithms for phase retrieval
Marchesini, S. (2007) · Review of Scientific Instruments · doi:10.1063/1.2403783 · Cited by 573
Phase Retrieval via Matrix Completion
Candès, E. J., Eldar, Y. C., Strohmer, T., & Voroninski, V. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/110848074 · Cited by 565
Self-citationHayes, M. (1982) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1982.1163863 · Cited by 431
Phase retrieval from coded diffraction patterns
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2014.09.004 · Cited by 387
Self-citationYang, G.-Z., Dong, B.-Z., Gu, B.-Y., Zhuang, J.-Y., & Ersoy, O. K. (1994) · Applied Optics · doi:10.1364/ao.33.000209 · Cited by 373
High Resolution 3D X-Ray Diffraction Microscopy
Miao, J., Ishikawa, T., Johnson, B., Anderson, E. H., Lai, B., & Hodgson, K. O. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.088303 · Cited by 331
Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns
Candès, E. J., & Li, X. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-013-9162-z · Cited by 292
Self-citationThe LASSO Risk for Gaussian Matrices
Bayati, M., & Montanari, A. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2174612 · Cited by 277
Miao, J., Ishikawa, T., Shen, Q., & Earnest, T. (2008) · Annual Review of Physical Chemistry · doi:10.1146/annurev.physchem.59.032607.093642 · Cited by 241
Quantum Tomography under Prior Information
Heinosaari, T., Mazzarella, L., & Wolf, M. M. (2013) · Communications in Mathematical Physics · doi:10.1007/s00220-013-1671-8 · Cited by 228
Fast global convergence of gradient methods for high-dimensional statistical recovery
Agarwal, A., Negahban, S., & Wainwright, M. J. (2012) · The Annals of Statistics · doi:10.1214/12-aos1032 · Cited by 204
Compressive phase retrieval via generalized approximate message passing
Schniter, P., & Rangan, S. (2012) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2012.6483302 · Cited by 66
Cited by
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
Sun, Y., Babu, P., & Palomar, D. P. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2601299 · Cited by 1,820
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Chen, Y., & Candès, E. J. (2017) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21638 · Cited by 477
Self-citationAn Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
Soltanolkotabi, M., Javanmard, A., & Lee, J. D. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2854560 · Cited by 356
Self-citation
Metadata
- Authors
- Candès, E. J., Li, X., & Soltanolkotabi, M.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2015-04
- Volume
- 61
- Issue
- 4
- Pages
- 1985-2007
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2142949395
- Cited by
- 1,049
- References
- 26
- FWCI
- 79.22
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.