{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T18:40:23Z","timestamp":1785177623313,"version":"3.55.0"},"reference-count":46,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"1","license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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 Signal Process. Lett."],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1109\/lsp.2014.2345761","type":"journal-article","created":{"date-parts":[[2014,8,7]],"date-time":"2014-08-07T18:48:11Z","timestamp":1407437291000},"page":"45-49","source":"Crossref","is-referenced-by-count":63,"title":["On the Computational Intractability of Exact and Approximate Dictionary Learning"],"prefix":"10.1109","volume":"22","author":[{"given":"Andreas M.","family":"Tillmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref39","first-page":"399","author":"arora","year":"1996","journal-title":"Approximation Algorithms for NP-Hard Problems"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"ref33","first-page":"37.1","article-title":"Exact recovery of sparsely-used dictionaries","volume":"23","author":"spielman","year":"2012","journal-title":"J Mach Learn Res"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"ref31","author":"coleman","year":"1984","journal-title":"?The sparse null space basis problem ?"},{"key":"ref30","doi-asserted-by":"crossref","DOI":"10.21236\/ADA131387","author":"mccormick","year":"1983","journal-title":"A combinatorial approach to some sparse matrix problems"},{"key":"ref37","first-page":"116","volume":"652","author":"buhrman","year":"1992","journal-title":"Proc FSTTCS 12"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1002\/9781118600207.ch13"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"ref34","article-title":"Learning sparsely used overcomplete dictionaries via alternating minimization","author":"agarwal","year":"2013"},{"key":"ref10","author":"tillmann","year":"2013","journal-title":"Computational aspects of compressed sensing"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_16"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.06.035"},{"key":"ref12","first-page":"19","article-title":"Online learning for matrix factorization and sparse coding","volume":"11","author":"mairal","year":"2010","journal-title":"J Mach Learn Res"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2006.881969"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1051\/0004-6361\/201220752"},{"key":"ref15","article-title":"Dictionary learning for deblurring and digital zoom","author":"couzinie-devy","year":"2011"},{"key":"ref16","article-title":"Regularized dictionary learning for sparse approximation","author":"yaghoobi","year":"2008","journal-title":"Proc EUSIPCO"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2011.2157892"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2245663"},{"key":"ref19","first-page":"v\/293","article-title":"Learning unions of orthonormal bases with thresholded singular value decompositon","volume":"5","author":"lesage","year":"2005","journal-title":"Proc IEEE ICASSP?05"},{"key":"ref28","article-title":"More algorithms for provable dictionary learning","author":"arora","year":"2014"},{"key":"ref4","author":"garey","year":"1979","journal-title":"Computers and Intractability A Guide to the Theory of NP-Completeness"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2278158"},{"key":"ref3","year":"2012","journal-title":"Compressed Sensing Theory and Applications"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00115-1"},{"key":"ref29","volume":"21","author":"korte","year":"2011","journal-title":"Combinatorial Optimization Theory and Algorithms"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1993.342465"},{"key":"ref7","article-title":"On the complexity of designing compact perceptrons and some consequences","author":"amaldi","year":"1999","journal-title":"Proc 4th Int Symp Artificial Intell Math"},{"key":"ref2","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":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2014.6854604"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2036477"},{"key":"ref45","first-page":"294","article-title":"Efficient probabilistically checkable proofs with applications to approximation problems","author":"bellare","year":"1993","journal-title":"Proc 25th ACM Symp Theory Comput"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1999.760624"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74494-8_51"},{"key":"ref42","article-title":"Analysis operator learning for overcomplete cosparse representations","author":"yaghoobi","year":"2011","journal-title":"Proc EUSIPCO"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2006.881199"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2012.2226445"},{"key":"ref23","author":"aharon","year":"2006","journal-title":"Overcomplete dictionaries for sparse representation of signals"},{"key":"ref44","article-title":"The projection games conjecture and the NP-hardness of ln <formula formulatype=\"inline\"><tex Notation=\"TeX\">$n$<\/tex><\/formula>-approximating set-cover","author":"moshkovitz","year":"2014"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1162\/089976603762552951"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2014.6853755"},{"key":"ref25","doi-asserted-by":"crossref","first-page":"3523","DOI":"10.1109\/TIT.2010.2048466","article-title":"Dictionary identification?sparse matrix-factorization via <formula formulatype=\"inline\"><tex Notation=\"TeX\">${\\ell _1}$<\/tex><\/formula>-minimization","volume":"56","author":"gribonval","year":"2010","journal-title":"IEEE Trans Inf Theory"}],"container-title":["IEEE Signal Processing Letters"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/97\/6876233\/06873279.pdf?arnumber=6873279","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T16:50:40Z","timestamp":1642006240000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/6873279\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":46,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.1109\/lsp.2014.2345761","relation":{},"ISSN":["1070-9908","1558-2361"],"issn-type":[{"value":"1070-9908","type":"print"},{"value":"1558-2361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}