{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:13:11Z","timestamp":1792797191940,"version":"4.5.0"},"reference-count":124,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"2","license":[{"start":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T00:00:00Z","timestamp":1485907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T00:00:00Z","timestamp":1485907200000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T00:00:00Z","timestamp":1485907200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T00:00:00Z","timestamp":1485907200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000006","name":"ONR","doi-asserted-by":"publisher","award":["N00014-13-1-0492"],"award-info":[{"award-number":["N00014-13-1-0492"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1343282"],"award-info":[{"award-number":["1343282"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF 1527809"],"award-info":[{"award-number":["CCF 1527809"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS 1546411"],"award-info":[{"award-number":["IIS 1546411"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Moore and Sloan Foundations","id":[{"id":"https:\/\/ror.org\/052csg198","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1109\/tit.2016.2632162","type":"journal-article","created":{"date-parts":[[2016,11,23]],"date-time":"2016-11-23T15:25:20Z","timestamp":1479914720000},"page":"853-884","source":"Crossref","is-referenced-by-count":139,"title":["Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture"],"prefix":"10.1109","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2017-5903","authenticated-orcid":false,"given":"Ju","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5616-7393","authenticated-orcid":false,"given":"Qing","family":"Qu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Wright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref39","article-title":"Learning sparsely used overcomplete dictionaries via alternating minimization","author":"agarwal","year":"2013"},{"key":"ref38","first-page":"37.1","article-title":"Exact recovery of sparsely-used dictionaries","author":"spielman","year":"2012","journal-title":"Proc 25th Annu Conf Learn Theory"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2005.1416298"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2013.420"},{"key":"ref31","first-page":"1","article-title":"Mathematics of sparsity (and a few other things)","author":"cand\u00e8s","year":"2014","journal-title":"Proc Int Congr Math"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau005"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0701-9"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0449"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501703105"},{"key":"ref34","volume":"23","author":"bertsekas","year":"1989","journal-title":"Parallel and Distributed Computation Numerical Methods"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9135-7"},{"key":"ref27","article-title":"Square deal: Lower bounds and improved relaxations for tensor recovery","author":"mu","year":"2013"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21432"},{"key":"ref20","article-title":"Identifiability and stability in blind deconvolution under minimal assumptions","author":"li","year":"2015"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2009.0152"},{"key":"ref21","article-title":"Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems","author":"kech","year":"2016"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"ref23","article-title":"New null space results and recovery thresholds for matrix rank minimization","author":"oymak","year":"2010"},{"key":"ref101","article-title":"Provable tensor methods for learning mixtures of generalized linear models","author":"sedghi","year":"2014"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9191-2"},{"key":"ref100","article-title":"Provable bounds for learning some deep representations","author":"arora","year":"2013"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1306110110"},{"key":"ref50","author":"absil","year":"2009","journal-title":"Optimization Algorithms on Matrix Manifolds"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588294"},{"key":"ref59","article-title":"Local identifiability of $\\ell_{1}$ -minimization dictionary learning: A sufficient and almost necessary condition","author":"wu","year":"2015"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.54"},{"key":"ref57","article-title":"Dictionary learning and tensor decomposition via the sum-of-squares method","author":"barak","year":"2014"},{"key":"ref56","article-title":"Convergence radius and sample complexity of ITKM algorithms for dictionary learning","author":"schnass","year":"2015"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.01.005"},{"key":"ref54","article-title":"Local identification of overcomplete dictionaries","author":"schnass","year":"2014"},{"key":"ref53","article-title":"When can dictionary learning uniquely recover sparse data from subsamples?","author":"hillar","year":"2011"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.06.035"},{"key":"ref40","article-title":"New algorithms for learning incoherent and overcomplete dictionaries","author":"arora","year":"2013"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002816"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2632149"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03413-8_6"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s102080010029"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2009.935453"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-005-0179-9"},{"key":"ref7","first-page":"87","article-title":"New ties between computational harmonic analysis and approximation theory","author":"cand\u00e8s","year":"2002","journal-title":"Approximation Theory X Wavelets Splines and Applications"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/18.720544"},{"key":"ref46","first-page":"3401","article-title":"Finding a sparse vector in a subspace: Linear sparsity using alternating directions","author":"qu","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1162\/089976601300014385"},{"key":"ref48","first-page":"797","article-title":"Escaping from saddle points—Online stochastic gradient for tensor decomposition","author":"ge","year":"2015","journal-title":"Proc 28th Conf Learn Theory"},{"key":"ref47","article-title":"When are nonconvex problems not scary?","author":"sun","year":"2015"},{"key":"ref42","article-title":"More algorithms for provable dictionary learning","author":"arora","year":"2014"},{"key":"ref41","article-title":"A clustering approach to learn sparsely-used overcomplete dictionaries","author":"agarwal","year":"2013"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau007"},{"key":"ref43","article-title":"Simple, efficient, and neural algorithms for sparse coding","author":"arora","year":"2015"},{"key":"ref124","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"ref73","article-title":"Provable sparse tensor decomposition","author":"sun","year":"2015"},{"key":"ref72","article-title":"Statistical consistency and asymptotic normality for high-dimensional robust M-estimators","author":"loh","year":"2015"},{"key":"ref71","article-title":"Support recovery without incoherence: A case for nonconvex regularization","author":"loh","year":"2014"},{"key":"ref70","article-title":"High dimensional expectation-maximization algorithm: Statistical optimization and asymptotic normality","author":"wang","year":"2014"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.75"},{"key":"ref77","first-page":"638","article-title":"Fast matrix completion without the condition number","author":"hardt","year":"2014","journal-title":"Proceedings of The 27th Conference on Learning Theory"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488693"},{"key":"ref78","first-page":"1107","article-title":"Non-convex robust PCA","author":"netrapalli","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref79","article-title":"Fast exact matrix completion with finite samples","author":"jain","year":"2014"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2069250"},{"key":"ref62","first-page":"36","article-title":"Sparsity-based generalization bounds for predictive sparse coding","author":"mehta","year":"2013","journal-title":"Proc Int Conf Mach Learn (ICML)"},{"key":"ref61","first-page":"3259","article-title":"The sample complexity of dictionary learning","volume":"12","author":"vainsencher","year":"2011","journal-title":"J Mach Learn Res"},{"key":"ref63","article-title":"Sample complexity of dictionary learning and other matrix factorizations","author":"gribonval","year":"2013"},{"key":"ref64","article-title":"Sparse and spurious: Dictionary learning with noise and outliers","author":"gribonval","year":"2014"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_16"},{"key":"ref66","first-page":"2726","article-title":"High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity","author":"loh","year":"2011","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref67","first-page":"476","article-title":"Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima","author":"loh","year":"2013","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref68","article-title":"Nonconvex statistical optimization: Minimax-optimal sparse PCA in polynomial time","author":"wang","year":"2014"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/SAMPTA.2015.7148922"},{"key":"ref69","article-title":"Statistical guarantees for the EM algorithm: From population to sample-based analysis","author":"balakrishnan","year":"2014"},{"key":"ref1","first-page":"2351","article-title":"Complete dictionary recovery using nonconvex optimization","author":"sun","year":"2015","journal-title":"Proc Int Conf Mach Learn (ICML)"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1109\/72.761722"},{"key":"ref95","article-title":"Dropping convexity for faster semi-definite optimization","author":"bhojanapalli","year":"2015"},{"key":"ref108","first-page":"2375","article-title":"Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders","author":"arora","year":"2012","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref94","article-title":"Computing matrix squareroot via non convex local search","author":"jain","year":"2015"},{"key":"ref107","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548495"},{"key":"ref93","article-title":"Near optimal compressed sensing of a class of sparse low-rank matrices via sparse power factorization","author":"lee","year":"2013"},{"key":"ref106","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(94)90029-9"},{"key":"ref92","article-title":"Alternating minimization for mixed linear regression","author":"yi","year":"2013"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1002\/0471221317"},{"key":"ref91","article-title":"Tensor vs matrix methods: Robust tensor decomposition under block sparse perturbations","author":"anandkumar","year":"2015"},{"key":"ref104","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(00)00026-5"},{"key":"ref90","article-title":"Analyzing tensor power method dynamics in overcomplete regime","author":"anandkumar","year":"2014"},{"key":"ref103","first-page":"855","article-title":"On the computational efficiency of training neural networks","author":"livni","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref102","article-title":"Sparse matrix factorization","author":"neyshabur","year":"2013"},{"key":"ref111","article-title":"Global optimality of local search for low rank matrix recovery","author":"bhojanapalli","year":"2016"},{"key":"ref112","article-title":"Matrix completion has no spurious local minimum","author":"ge","year":"2016"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541725"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.06.007"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213994"},{"key":"ref96","first-page":"3858","article-title":"L0 norm based dictionary learning by proximal methods with global convergence","author":"bao","year":"2014","journal-title":"Proc IEEE Conf Comput Vis Pattern Recognit (CVPR)"},{"key":"ref97","first-page":"302","article-title":"A convergent incoherent dictionary learning algorithm for sparse coding","author":"bao","year":"2014","journal-title":"Proc Eur Conf Comput Vis"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1038\/381607a0"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0042-6989(97)00169-7"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7011-4"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1561\/0600000058"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2048466"},{"key":"ref15","article-title":"On the local correctness of $\\ell ^{1}$ -minimization for dictionary learning","author":"geng","year":"0","journal-title":"IEEE Trans Inf Theory"},{"key":"ref118","article-title":"No bad local minima: Data independent training error guarantees for multilayer neural networks","author":"soudry","year":"2016"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2294644"},{"key":"ref82","article-title":"Low-rank solutions of linear matrix equations via procrustes flow","author":"tu","year":"2015"},{"key":"ref117","article-title":"Deep learning without poor local minima","author":"kawaguchi","year":"2016"},{"key":"ref17","article-title":"Identifiability scaling laws in bilinear inverse problems","author":"choudhary","year":"2014"},{"key":"ref81","article-title":"A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements","author":"zheng","year":"2015"},{"key":"ref18","article-title":"Approximating the little Grothendieck problem over the orthogonal and unitary groups","author":"bandeira","year":"2013"},{"key":"ref84","first-page":"2796","article-title":"Phase retrieval using alternating minimization","author":"netrapalli","year":"2013","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref119","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895290954"},{"key":"ref19","article-title":"Tight hardness of the non-commutative Grothendieck problem","author":"bri\u00ebt","year":"2014"},{"key":"ref83","article-title":"Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees","author":"chen","year":"2015"},{"key":"ref114","doi-asserted-by":"publisher","DOI":"10.1137\/16M105808X"},{"key":"ref113","article-title":"The nonconvex Burer–Monteiro approach works on smooth semidefinite programs","author":"boumal","year":"2016"},{"key":"ref116","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(89)90014-2"},{"key":"ref80","article-title":"Guaranteed matrix completion via non-convex factorization","author":"sun","year":"2014"},{"key":"ref115","article-title":"On the low-rank approach for semidefinite programs arising in synchronization and community detection","author":"bandeira","year":"2016"},{"key":"ref120","author":"folland","year":"1999","journal-title":"Real Analysis Modern Techniques and Their Applications"},{"key":"ref89","article-title":"Guaranteed non-orthogonal tensor decomposition via alternating rank-1 updates","author":"anandkumar","year":"2014"},{"key":"ref121","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034241"},{"key":"ref122","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"ref123","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-8176-4948-7","author":"foucart","year":"2013","journal-title":"A Mathematical Introduction to Compressive Sensing"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2399924"},{"key":"ref86","article-title":"Solving random quadratic systems of equations is nearly as easy as solving linear systems","author":"chen","year":"2015"},{"key":"ref87","article-title":"The local convexity of solving systems of quadratic equations","author":"white","year":"2015"},{"key":"ref88","first-page":"1431","article-title":"Provable tensor factorization with missing data","author":"jain","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/ieeexplore.ieee.org\/ielaam\/18\/7823065\/7755794-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/7823065\/07755794.pdf?arnumber=7755794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T14:52:11Z","timestamp":1649429531000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/7755794\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2]]},"references-count":124,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1109\/tit.2016.2632162","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2]]}}}