The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Open accessAbstract
We consider the fundamental problem of solving quadratic systems of equations in , and is unknown. We propose a novel method, which starts with an initial guess computed by means of a spectral method and proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach [13]. There are several key distinguishing features, most notably a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, better descent directions, and thus enhanced practical performance. On the theoretical side, we prove that for certain unstructured models of quadratic systems, our algorithms return the correct solution in linear time, i.e., in time proportional to reading the data {ai} and {yi} as soon as the ratio m/n between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems in which we only have and prove that our algorithms achieve a statistical accuracy, which is nearly unimprovable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size—hence the title of this paper. For instance, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least squares problem of the same size. © 2016 Wiley Periodicals, Inc.
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
Advances in neural information processing systems 7
Cios, K., & Shields, M. (1997) · Neurocomputing · doi:10.1016/s0925-2312(97)90018-7 · Cited by 22,059
Phase retrieval algorithms: a comparison
Fienup, J. R. (1982) · Applied Optics · doi:10.1364/ao.21.002758 · Cited by 5,596
A practical algorithm for the determination of phase from image and diffraction plane pictures
Gerchberg, R. W. (1972) · Optik · Cited by 4,519
Trefethen, L. N., & Bau, III (1997) · doi:10.1137/1.9780898719574 · Cited by 3,301
Introduction to Nonparametric Estimation
Tsybakov, A. B. (2009) · Springer Series in Statistics · doi:10.1007/b13794 · Cited by 2,486
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Mitzenmacher, M., & Upfal, E. (2005) · Cambridge University Press eBooks · doi:10.1017/cbo9780511813603 · Cited by 1,733
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-citationThe Rotation of Eigenvectors by a Perturbation. III
Davis, C., & Kahan, W. M. (1970) · SIAM Journal on Numerical Analysis · doi:10.1137/0707001 · Cited by 1,175
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
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
Self-citationInternational Conference on Machine Learning (ICML-99).
Scheffer, T. (1999) · Künstliche Intell. · Cited by 1,003
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
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
Phase retrieval by iterated projections
Elser, V. (2003) · Journal of the Optical Society of America A · doi:10.1364/josaa.20.000040 · Cited by 737
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
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-citationGuaranteed 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
Self-citationCompressive Phase Retrieval via Generalized Approximate Message Passing
Schniter, P., & Rangan, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2386294 · Cited by 279
Sparse Signal Recovery from Quadratic Measurements via Convex Programming
Li, X., & Voroninski, V. (2013) · SIAM Journal on Mathematical Analysis · doi:10.1137/120893707 · Cited by 217
Phase Retrieval: Stability and Recovery GuaranteesPreprint
(n.d.) · Cited by 207
Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
Chen, Y., Chi, Y., & Goldsmith, A. J. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2429594 · Cited by 205
Self-citationLow rank matrix recovery from rank one measurements
Kueng, R., Rauhut, H., & Terstiege, U. (2017) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2015.07.007 · Cited by 173
Consistent Shape Maps via Semidefinite Programming
Huang, Q., & Guibas, L. (2013) · Computer Graphics Forum · doi:10.1111/cgf.12184 · Cited by 170
Painless Reconstruction from Magnitudes of Frame Coefficients
Balan, R., Bodmann, B. G., Casazza, P. G., & Edidin, D. (2009) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-009-9065-1 · Cited by 169
When Are Nonconvex Problems Not Scary?Preprint
Sun, J., Qu, Q., & Wright, J. N. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.06096 · Cited by 166
Consistent shape maps via semidefinite programming
Qi-xing Huang, A., & Guibas, L. J. (2013) · doi:10.5555/2600289.2600314 · Cited by 149
Phase Retrieval with Polarization
Alexeev, B., Bandeira, A. S., Fickus, M. C., & Mixon, D. G. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/12089939x · Cited by 135
Zheng, Q., & Lafferty, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.06081 · Cited by 130
A Partial Derandomization of PhaseLift Using Spherical Designs
Gross, D., Krahmer, F., & Kueng, R. (2014) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-014-9361-2 · Cited by 127
Stable Optimizationless Recovery from Phaseless Linear Measurements
Demanet, L., & Hand, P. (2013) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-013-9305-2 · Cited by 124
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
Simple, Efficient, and Neural Algorithms for Sparse CodingPreprint
Arora, S., Ge, R., Ma, T., & Moitra, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.00778 · Cited by 106
ROP: Matrix recovery via rank-one projectionsPreprint
Cai, T., & Zhang, A. R. (2016) · Cited by 106
ROP: Matrix recovery via rank-one projections
Cai, T. T., & Zhang, A. (2014) · The Annals of Statistics · doi:10.1214/14-aos1267 · Cited by 91
Fast matrix completion without the condition numberPreprint
Hardt, M., & Wootters, M. K. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.4070 · Cited by 84
Multireference alignment using semidefinite programming
Bandeira, A. S., Charikar, M., Singer, A., & Zhu, A. (2014) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2554797.2554839 · Cited by 83
Complete dictionary recovery over the sphere
Sun, J., Qu, Q., & Wright, J. N. (2015) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2015.7148922 · Cited by 78
Low-rank Matrix Completion using Alternating MinimizationPreprint
Jain, P., Netrapalli, P., & Sanghavi, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.0467 · 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
Low rank matrix recovery from few orthonormal basis measurements
Kueng, R. (2015) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2015.7148921 · Cited by 14
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
Self-citationSolving Systems of Random Quadratic Equations via Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Eldar, Y. C. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756858 · Cited by 330
Stochastic Model-Based Minimization of Weakly Convex Functions
Davis, D., & Drusvyatskiy, D. (2019) · SIAM Journal on Optimization · doi:10.1137/18m1178244 · Cited by 258
Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632162 · Cited by 213
Nonconvex Demixing From Bilinear Measurements
Dong, J., & Shi, Y. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2864660 · Cited by 37
Metadata
- Authors
- Chen, Y., & Candès, E. J.
- Venue
- Communications on Pure and Applied Mathematics
- Publisher
- Wiley
- Published
- 2016-04-06
- Volume
- 70
- Issue
- 5
- Pages
- 822-883
- ISSN
- 0010-3640 (ISSN-L)
- 1097-0312
- OpenAlex
- W221278985
- Cited by
- 477
- References
- 44
- FWCI
- 67.07
- 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.