{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T03:14:26Z","timestamp":1791947666203,"version":"4.3.4"},"reference-count":56,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2016,4,6]],"date-time":"2016-04-06T00:00:00Z","timestamp":1459900800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Comm Pure Appl Math"],"published-print":{"date-parts":[[2017,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider the fundamental problem of solving quadratic systems of equations in\n                    <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/cpa21638-math-0001.png\" xlink:title=\"urn:x-wiley:00103640:media:cpa21638:cpa21638-math-0001\"\/>\n                    , and\n                    <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/cpa21638-math-0002.png\" xlink:title=\"urn:x-wiley:00103640:media:cpa21638:cpa21638-math-0002\"\/>\n                    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 {\n                    <jats:italic>a<\/jats:italic>\n                    <jats:sub>\n                      <jats:italic>i<\/jats:italic>\n                    <\/jats:sub>\n                    } and {\n                    <jats:italic>y<\/jats:italic>\n                    <jats:sub>\n                      <jats:italic>i<\/jats:italic>\n                    <\/jats:sub>\n                    } as soon as the ratio\n                    <jats:italic>m<\/jats:italic>\n                    \/\n                    <jats:italic>n<\/jats:italic>\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\n                    <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/cpa21638-math-0003.png\" xlink:title=\"urn:x-wiley:00103640:media:cpa21638:cpa21638-math-0003\"\/>\n                    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\u2014hence 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. \u00a9 2016 Wiley Periodicals, Inc.\n                  <\/jats:p>","DOI":"10.1002\/cpa.21638","type":"journal-article","created":{"date-parts":[[2016,4,10]],"date-time":"2016-04-10T10:14:24Z","timestamp":1460283264000},"page":"822-883","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":243,"title":["Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems"],"prefix":"10.1002","volume":"70","author":[{"given":"Yuxin","family":"Chen","sequence":"first","affiliation":[{"name":"Packard Electrical Engineering Building, Room 338 350 Serra Mall Stanford University Stanford CA 94305 USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emmanuel J.","family":"Cand\u00e8s","sequence":"additional","affiliation":[{"name":"Department of Statistics Stanford University 390 Serra Mall, Sequoia Hall Stanford CA 94305 USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2016,4,6]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/12089939X"},{"key":"e_1_2_1_3_1","unstructured":"Arora S.;Ge R.;Ma T.;Moitra A.Simple efficient and neural algorithms for sparse coding. Preprint 2015. arxiv:1503.00778 [cs.LG]"},{"key":"e_1_2_1_4_1","unstructured":"Bahmani S.;Romberg J.Efficient compressive phase retrieval with constrained sensing vectors. Preprint 2015. arxiv:1507.08254 [cs.IT]"},{"key":"e_1_2_1_5_1","unstructured":"Balakrishnan S.;Wainwright M. J.;Yu B.Statistical guarantees for the EM algorithm: From population to sample\u2010based analysis. Preprint 2014. arxiv:1408.2156 [math.ST]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-009-9065-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2013.10.002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554839"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1267"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9162-z"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.09.004"},{"key":"e_1_2_1_13_1","unstructured":"Cand\u00e8s E. J.;Li X.;Soltanolkotabi M.Phase retrieval via Wirtinger flow 2014Available at:http:\/\/www-bcf.usc.edu\/~soltanol\/PRWF.html."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2399924"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21432"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Chen Y.;Cand\u00e8s E. J.Supplemental materials for: \u201cSolving random quadratic systems of equations is nearly as easy as solving linear systems\u201d(2015). Available at:http:\/\/statweb.stanford.edu\/~candes\/publications.html","DOI":"10.1002\/cpa.21638"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2429594"},{"key":"e_1_2_1_18_1","unstructured":"Chen Y.;Guibas L. J.;Huang Q.Near\u2010optimal joint optimal matching via convex relaxation.International Conference on Machine Learning (ICML)(2014) 100\u2013108."},{"key":"e_1_2_1_19_1","unstructured":"Chen Y.;Yi X.;Caramanis C.A convex formulation for mixed regression with two components: Minimax optimal rates. Preprint 2013. arxiv:1312.7006 [stat.ML]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0707001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-013-9305-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2013.08.003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.20.000040"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1364\/AO.21.002758"},{"key":"e_1_2_1_25_1","first-page":"237","article-title":"A practical algorithm for the determination of phase from image and diffraction plane pictures","volume":"35","author":"Gerchberg R. W.","year":"1972","journal-title":"Optik"},{"key":"e_1_2_1_26_1","unstructured":"Gross D.;Krahmer F.;Kueng R.Improved recovery guarantees for phase retrieval from coded diffraction patterns. Preprint 2014. arxiv:1402.6286 [cs.IT]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-014-9361-2"},{"key":"e_1_2_1_28_1","unstructured":"Hardt M.;Wootters M.Fast matrix completion without the condition number.Conference on Learning Theory(2014) 638\u2013678."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12184"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6283508"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Jain P.;Netrapalli P.;Sanghavi S.Low\u2010rank matrix completion using alternating minimization (extended abstract).STOC'13\u2014Proceedings of the 2013 ACM Symposium on Theory of Computing 665\u2013674.ACM New York 2013. doi:10.1145\/2488608.2488693","DOI":"10.1145\/2488608.2488693"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Kueng R.;Rauhut H.;Terstiege U.Low rank matrix recovery from rank one measurements. Preprint 2014. arxiv:1410.6913 [cs.IT]","DOI":"10.1109\/SAMPTA.2015.7148921"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/120893707"},{"key":"e_1_2_1_35_1","unstructured":"Marchesin S.;Tu Y.;Wu H.Alternating projection ptychographic imaging and phase synchronization. Preprint 2014. arxiv:1402.0550 [math.OC]"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2015.2448516"},{"key":"e_1_2_1_38_1","unstructured":"Netrapalli P.;Niranjan U.;Sanghavi S.;Anandkumar A.;Jain P.:Non\u2010convex robust PCA.Advances in Neural Information Processing Systems(2014) 1107\u20131115."},{"key":"e_1_2_1_39_1","volume-title":"Numerical optimization","author":"Nocedal J.","year":"2006"},{"key":"e_1_2_1_40_1","unstructured":"Ohlsson H.;Yang A.;Dong R.;Sastry S. S.Compressive phase retrieval from squared output measurements via semidefinite programming. Preprint 2011. arxiv:1111.6323 [math.ST]"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2014.7025351"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2014.2386294"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2297687"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2014.2352673"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1364\/OE.19.014807"},{"key":"e_1_2_1_46_1","volume-title":"Algorithms and theory for clustering and nonconvex quadratic programming","author":"Soltanolkotabi M.","year":"2014"},{"key":"e_1_2_1_47_1","unstructured":"Sun R.;Luo Z.Guaranteed matrix completion via non\u2010convex factorization. Preprint 2014. arxiv:1411.8003 [cs.LG]"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Sun J.;Qu Q.;Wright J.Complete dictionary recovery using nonconvex optimization.International Conference on Machine Learning(2015) 2351\u20132360.","DOI":"10.1109\/SAMPTA.2015.7148922"},{"key":"e_1_2_1_49_1","unstructured":"Sun J.;Qu Q.;Wright J.When are nonconvex problems not scary?Preprint 2015. arxiv:1510.06096 [math.OC]"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/b13794"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511794308.006"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0738-9"},{"key":"e_1_2_1_54_1","unstructured":"Wei K.Phase retrieval via Kaczmarz methods. Preprint 2015. arxiv:1502.01822 [math.NA]"},{"key":"e_1_2_1_55_1","unstructured":"White C. D.;Ward R.;Sanghavi S.The local convexity of solving quadratic equations. Preprint 2015. arxiv:1506.07868 [math.NA]"},{"key":"e_1_2_1_56_1","unstructured":"Yi X.;Caramanis C.;Sanghavi S.Alternating minimization for mixed linear regression. Preprint 2013. arxiv:1310.3745 [stat.ML]"},{"key":"e_1_2_1_57_1","first-page":"109","article-title":"A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements","volume":"28","author":"Zheng Q.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Communications on Pure and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpa.21638","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpa.21638","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpa.21638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T09:17:22Z","timestamp":1696583842000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpa.21638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,6]]},"references-count":56,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["10.1002\/cpa.21638"],"URL":"https:\/\/doi.org\/10.1002\/cpa.21638","archive":["Portico"],"relation":{},"ISSN":["0010-3640","1097-0312"],"issn-type":[{"value":"0010-3640","type":"print"},{"value":"1097-0312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,6]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}