The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
Open accessAbstract
This paper presents a new algorithm, termed truncated amplitude flow (TAF), to recover an unknown vector x from a system of quadratic equations of the form yi= |〈ai, x〉|2, where ai's are given random measurement vectors. This problem is known to be NP-hard in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adapts the amplitude based empirical loss function and proceeds in two stages. In the first stage, we introduce an orthogonality-promoting initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable truncated generalized gradient iterations, which are able to handle the rather challenging nonconvex and nonsmooth amplitude based objective function. In particular, when vectors x and ai's are real valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.
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
Iterative Methods for Sparse Linear Systems
Saad, Y. (2003) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718003 · Cited by 13,790
Optimization and Nonsmooth Analysis
Clarke, F. H. (1990) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971309 · Cited by 10,264
A practical algorithm for the determination of phase from image and diffraction plane pictures
Gerchberg, R. W. (1972) · Optik · Cited by 4,519
Rockafellar, R. T., & Wets, R. J. B. (1998) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-642-02431-3 · Cited by 4,086
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
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
Minimization Methods for Non-Differentiable Functions
Shor, N. Z. (1985) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-82118-9 · Cited by 1,551
Generalized gradients and applications
Clarke, F. H. (1975) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1975-0367131-6 · Cited by 1,206
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
Phase Retrieval with Application to Optical Imaging: A contemporary overview
Shechtman, Y., Eldar, Y. C., Cohen, O., Chapman, H. N., Miao, J., & Segev, M. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2352673 · Cited by 1,131
Self-citationMost Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2399924 · Cited by 1,049
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
Adaptive estimation of a quadratic functional by model selection
Laurent, B., & Massart, P. (2000) · The Annals of Statistics · doi:10.1214/aos/1015957395 · Cited by 995
Matrix 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
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
Matrix completion from a few entries
Keshavan, R. H., Oh, S., & Montanari, A. (2009) · 2009 IEEE International Symposium on Information Theory · doi:10.1109/isit.2009.5205567 · Cited by 650
Phase recovery, MaxCut and complex semidefinite programming
Waldspurger, I., d’Aspremont, A., & Mallat, S. (2015) · Mathematical Programming · doi:10.1007/s10107-013-0738-9 · Cited by 573
Phase Retrieval Using Alternating Minimization
Netrapalli, P., Jain, P., & Sanghavi, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2448516 · Cited by 535
Quadratic programming with one negative eigenvalue is NP-hard
Pardalos, P. M., & Vavasis, S. A. (1991) · Journal of Global Optimization · doi:10.1007/bf00120662 · Cited by 510
Phase Retrieval via Matrix Completion
Candès, E. J., Eldar, Y. C., Strohmer, T., & Voroninski, V. (2015) · SIAM Review · doi:10.1137/151005099 · Cited by 481
Self-citationSolving 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
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
Experimental robustness of Fourier ptychography phase retrieval algorithms
Yeh, L.-H., Dong, J., Zhong, J., Tian, L., Chen, M., Tang, G., Soltanolkotabi, M., & Waller, L. (2015) · Optics Express · doi:10.1364/oe.23.033214 · Cited by 320
Guaranteed Matrix Completion via Non-Convex Factorization
Sun, R., & Luo, Z.-Q. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2598574 · Cited by 309
Saving phase: Injectivity and stability for phase retrieval
Bandeira, A. S., Cahill, J., Mixon, D. G., & Nelson, A. A. (2014) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2013.10.002 · Cited by 301
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
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
Distributions of Angles in Random Packing on Spheres
Cai, T., Fan, J., & Jiang, T. (2013) · Journal of Machine Learning Research · doi:10.48550/arxiv.1306.0256 · Cited by 231
An algebraic characterization of injectivity in phase retrieval
Conca, A., Edidin, D., Hering, M., & Vinzant, C. (2014) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2014.06.005 · Cited by 217
Phase Retrieval: Stability and Recovery GuaranteesPreprint
(n.d.) · Cited by 207
A Geometric Analysis of Phase Retrieval
Sun, J., Qu, Q., & Wright, J. (2018) · Foundations of Computational Mathematics · doi:10.1007/s10208-017-9365-9 · Cited by 189
Low-rank Solutions of Linear Matrix Equations via Procrustes FlowPreprint
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., & Recht, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.03566 · Cited by 180
Rapid, robust, and reliable blind deconvolution via nonconvex optimization
Li, X., Ling, S., Strohmer, T., & Wei, K. (2019) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2018.01.001 · Cited by 176
Sparse Phase Retrieval via Truncated Amplitude Flow
Wang, G., Zhang, L., Giannakis, G. B., Akçakaya, M., & Chen, J. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2771733 · Cited by 157
Self-citationPhase retrieval: an overview of recent developments
Jaganathan, K., Eldar, Y. C., & Hassibi, B. (2016) · CaltechAUTHORS (California Institute of Technology) · doi:10.1201/9781315371474-26 · Cited by 132
Self-citationPhase Retrieval: An Overview of Recent DevelopmentsPreprint
Jaganathan, K., Eldar, Y. C., & Hassibi, B. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.07713 · Cited by 121
Self-citationSolving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
Duchi, J. C., & Ruan, F. (2018) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iay015 · Cited by 117
Alternating projection, ptychographic imaging and phase synchronization
Marchesini, S., Tu, Y.-C., & Wu, H. (2015) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2015.06.005 · Cited by 106
Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study
Wei, K. (2015) · Inverse Problems · doi:10.1088/0266-5611/31/12/125008 · Cited by 96
Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
Jaganathan, K., Oymak, S., & Hassibi, B. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2656844 · Cited by 87
Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Chen, J. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2652392 · Cited by 55
Self-citationThe Local Convexity of Solving Systems of Quadratic Equations
Sanghavi, S., Ward, R., & White, C. D. (2016) · Results in Mathematics · doi:10.1007/s00025-016-0564-5 · Cited by 49
Phase Retrieval Using Feasible Point Pursuit: Algorithms and Cramér–Rao Bound
Qian, C., Sidiropoulos, N. D., Huang, K., Huang, L., & So, H. C. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2593688 · Cited by 35
The local convexity of solving systems of quadratic equationsPreprint
White, C. D., Sanghavi, S., & Ward, R. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.07868 · Cited by 32
Solving Most Systems of Random Quadratic Equations
Wang, G., Giannakis, G. B., Saad, Y. E.-M., et al. (2017) · neural information processing systems · Cited by 20
Self-citationA Clarification of the Cauchy Distribution
Lee, H.-Y., Park, H.-J., & Kim, H. (2014) · Communications for Statistical Applications and Methods · doi:10.5351/csam.2014.21.2.183 · Cited by 15
Cited by
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
Metadata
- Authors
- Wang, G., Giannakis, G. B., & Eldar, Y. C.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2018-02
- Volume
- 64
- Issue
- 2
- Pages
- 773-794
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2964262188
- Cited by
- 330
- References
- 48
- FWCI
- 36.67
- 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.