{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T14:04:29Z","timestamp":1777125869257,"version":"3.51.4"},"reference-count":60,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"2","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1109\/tit.2013.2290112","type":"journal-article","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T18:52:00Z","timestamp":1384887120000},"page":"1248-1259","source":"Crossref","is-referenced-by-count":239,"title":["The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing"],"prefix":"10.1109","volume":"60","author":[{"given":"Andreas M.","family":"Tillmann","sequence":"first","affiliation":[]},{"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-2.2.284"},{"key":"ref38","first-page":"2","article-title":"Full spark frames","volume":"3","author":"alexeev","year":"2011","journal-title":"J Fourier Anal Appl"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1995.1005"},{"key":"ref32","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1073\/pnas.0437847100","article-title":"Optimally sparse representation in general (non-orthogonal) dictionaries via <formula formulatype=\"inline\"><tex Notation=\"TeX\">$\\ell^{1}$<\/tex><\/formula> minimization","volume":"100","author":"donoho","year":"2003","journal-title":"P Nat Academy Sci USA"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0416-0"},{"key":"ref30","first-page":"1269","article-title":"Optimal solutions for sparse principal component analysis","volume":"9","author":"d'aspremont","year":"2008","journal-title":"J Mach Learn Res"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.21236\/ADA131387"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/0607059"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00254-G"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-002-0076-4"},{"key":"ref60","author":"cho","year":"2013","journal-title":"Precisely Verifying the Null Space Conditions in Compressed Sensing A Sandwiching Algorithm"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2016030"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.820031"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0417-z"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7011-4"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"ref20","author":"koiran","year":"2011","journal-title":"On the certification of the restricted isometry property"},{"key":"ref22","author":"berthet","year":"2013","journal-title":"Computational Lower Bounds for Sparse PCA"},{"key":"ref21","author":"koiran","year":"2012","journal-title":"Hidden cliques and the certification of the restricted isometry property"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/18.959265"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2248414"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00610-3"},{"key":"ref25","author":"zhang","year":"2008","journal-title":"Theory of compressive sensing via -minimization A non-RIP analysis and extensions"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90136-4"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00115-1"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1137\/060657704"},{"key":"ref57","author":"golub","year":"1996","journal-title":"Matrix Computations"},{"key":"ref56","volume":"1","author":"gill","year":"1991","journal-title":"Numerical Linear Algebra and Optimization"},{"key":"ref55","author":"berthet","year":"2012","journal-title":"Optimal detection of sparse principal components in high dimensions"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(88)90144-9"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1939-6"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2008.09.001"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2054730"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/110839072"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/100788884"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.04.002"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2009.5054839"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-1384809"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2054653"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.834793"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/050645506"},{"key":"ref19","first-page":"5129","article-title":"Computing performance guarantees for compressed sensing","author":"lee","year":"2008","journal-title":"Proc IEEE ICASSP"},{"key":"ref4","author":"garey","year":"1979","journal-title":"Computers and Intractability A Guide to the Theory of NP-Completeness"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-92920-0_6"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1109\/18.641542"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/090748160"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.2307\/2687152"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref42","volume":"3","author":"oxley","year":"1992","journal-title":"Matroid Theory"},{"key":"ref41","volume":"21","author":"korte","year":"2008","journal-title":"Combinatorial Optimization Theory and Algorithms"},{"key":"ref44","author":"de marchi","year":"1999","journal-title":"Generalized Vandermonde determinants Toeplitz matrices and Schur functions"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084251"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/6714461\/06658871.pdf?arnumber=6658871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T16:31:37Z","timestamp":1642005097000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/6658871\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":60,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1109\/tit.2013.2290112","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,2]]}}}