{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T14:26:26Z","timestamp":1775571986547,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,6,14]],"date-time":"2015-06-14T00:00:00Z","timestamp":1434240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,6,14]]},"DOI":"10.1145\/2746539.2746605","type":"proceedings-article","created":{"date-parts":[[2015,6,3]],"date-time":"2015-06-03T15:35:56Z","timestamp":1433345756000},"page":"143-151","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":64,"title":["Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method"],"prefix":"10.1145","author":[{"given":"Boaz","family":"Barak","sequence":"first","affiliation":[{"name":"Microsoft Research, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan A.","family":"Kelner","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"CoRR abs\/1310.7991","author":"Agarwal Alekh","year":"2013","unstructured":"Alekh Agarwal , Animashree Anandkumar , Prateek Jain , Praneeth Netrapalli , and Rashish Tandon , Learning sparsely used overcomplete dictionaries via alternating minimization , CoRR abs\/1310.7991 ( 2013 ). Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, and Rashish Tandon, Learning sparsely used overcomplete dictionaries via alternating minimization, CoRR abs\/1310.7991 (2013)."},{"key":"e_1_3_2_1_2_1","volume-title":"CoRR abs\/1309.1952","author":"Agarwal Alekh","year":"2013","unstructured":"Alekh Agarwal , Animashree Anandkumar , and Praneeth Netrapalli , Exact recovery of sparsely used overcomplete dictionaries , CoRR abs\/1309.1952 ( 2013 ). Alekh Agarwal, Animashree Anandkumar, and Praneeth Netrapalli, Exact recovery of sparsely used overcomplete dictionaries, CoRR abs\/1309.1952 (2013)."},{"key":"e_1_3_2_1_3_1","volume-title":"CoRR abs\/1401.0579","author":"Arora Sanjeev","year":"2014","unstructured":"Sanjeev Arora , Aditya Bhaskara , Rong Ge , and Tengyu Ma , More algorithms for provable dictionary learning , CoRR abs\/1401.0579 ( 2014 ). Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma, More algorithms for provable dictionary learning, CoRR abs\/1401.0579 (2014)."},{"key":"e_1_3_2_1_4_1","first-page":"926","volume-title":"NIPS","author":"Anandkumar Anima","year":"2012","unstructured":"Anima Anandkumar , Dean P. Foster , Daniel Hsu , Sham Kakade , and Yi-Kai Liu , A spectral algorithm for latent dirichlet allocation , NIPS , 2012 , pp. 926 -- 934 . Anima Anandkumar, Dean P. Foster, Daniel Hsu, Sham Kakade, and Yi-Kai Liu, A spectral algorithm for latent dirichlet allocation, NIPS, 2012, pp. 926--934."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.49"},{"key":"e_1_3_2_1_6_1","volume-title":"New algorithms for learning incoherent and overcomplete dictionaries, arXiv preprint 1308.6723","author":"Arora Sanjeev","year":"2013","unstructured":"Sanjeev Arora , Rong Ge , and Ankur Moitra , New algorithms for learning incoherent and overcomplete dictionaries, arXiv preprint 1308.6723 ( 2013 ), http:\/\/arxiv.org\/abs\/1308.6273. Sanjeev Arora, Rong Ge, and Ankur Moitra, New algorithms for learning incoherent and overcomplete dictionaries, arXiv preprint 1308.6723 (2013), http:\/\/arxiv.org\/abs\/1308.6273."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_1_8_1","first-page":"742","volume-title":"JMLR Proceedings","volume":"35","author":"Bhaskara Aditya","year":"2014","unstructured":"Aditya Bhaskara , Moses Charikar , and Aravindan Vijayaraghavan , Uniqueness of tensor decompositions with applications to polynomial identifiability, COLT (Maria-Florina Balcan and Csaba Szepesv\u00e1ri, eds.) , JMLR Proceedings , vol. 35 , JMLR.org, 2014 , pp. 742 -- 778 . Aditya Bhaskara, Moses Charikar, and Aravindan Vijayaraghavan, Uniqueness of tensor decompositions with applications to polynomial identifiability, COLT (Maria-Florina Balcan and Csaba Szepesv\u00e1ri, eds.), JMLR Proceedings, vol. 35, JMLR.org, 2014, pp. 742--778."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of International Congress of Mathematicians (ICM)","author":"Barak Boaz","year":"2014","unstructured":"Boaz Barak and David Steurer , Sum-of-squares proofs and the quest toward optimal algorithms , Proceedings of International Congress of Mathematicians (ICM) , 2014 , To appear. Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms, Proceedings of International Congress of Mathematicians (ICM), 2014, To appear."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(94)90029-9"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20124"},{"key":"e_1_3_2_1_13_1","volume-title":"October","author":"Demanet L.","year":"2013","unstructured":"L. Demanet and P. Hand , Recovering the Sparsest Element in a Subspace , October 2013 , Arxiv preprint 1310.1654. L. Demanet and P. Hand, Recovering the Sparsest Element in a Subspace, October 2013, Arxiv preprint 1310.1654."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.88.187904"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2006.881969"},{"key":"e_1_3_2_1_17_1","first-page":"41","volume-title":"Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference","volume":"19","author":"Theodoros Evgeniou Andreas Argyriou","year":"2007","unstructured":"Andreas Argyriou Theodoros Evgeniou and Massimiliano Pontil , Multi-task feature learning , Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference , vol. 19 , MIT Press , 2007 , pp. 41 -- 48 . Andreas Argyriou Theodoros Evgeniou and Massimiliano Pontil, Multi-task feature learning, Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference, vol. 19, MIT Press, 2007, pp. 41--48."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875529"},{"key":"e_1_3_2_1_19_1","volume-title":"STOC","author":"Goyal Navin","year":"2014","unstructured":"Navin Goyal , Santosh Vempala , and Ying Xiao , Fourier pca , STOC , 2014 , Also available as arXiv report 1306.5825. Navin Goyal, Santosh Vempala, and Ying Xiao, Fourier pca, STOC, 2014, Also available as arXiv report 1306.5825."},{"key":"e_1_3_2_1_20_1","unstructured":"Richard A Harshman Foundations of the parafac procedure: Models and conditions for an\" explanatory\" multimodal factor analysis.  Richard A Harshman Foundations of the parafac procedure: Models and conditions for an\" explanatory\" multimodal factor analysis."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792233.1792242"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/b96977"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(77)90069-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.893943"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88690-7_4"},{"key":"e_1_3_2_1_27_1","volume-title":"Advances in neural information processing systems 20","author":"Ranzato Y Marc'Aurelio","year":"2007","unstructured":"Y Marc'Aurelio Ranzato , Lan Boureau , and Yann LeCun , Sparse feature learning for deep belief networks , Advances in neural information processing systems 20 ( 2007 ), 1185--1192. Y Marc'Aurelio Ranzato, Lan Boureau, and Yann LeCun, Sparse feature learning for deep belief networks, Advances in neural information processing systems 20 (2007), 1185--1192."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9031-0"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1038\/381607a0"},{"key":"e_1_3_2_1_31_1","volume-title":"Network: computation in neural systems 7","author":"Olshausen Bruno A","year":"1996","unstructured":"Bruno A Olshausen and David J Field , Natural image statistics and efficient coding* , Network: computation in neural systems 7 ( 1996 ), no. 2, 333--339. Bruno A Olshausen and David J Field, Natural image statistics and efficient coding*, Network: computation in neural systems 7 (1996), no. 2, 333--339."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0042-6989(97)00169-7"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2006.377261"},{"key":"e_1_3_2_1_35_1","first-page":"5","article-title":"An approach to obtaining global extremums in polynomial mathematical programming problems","volume":"23","author":"Shor NZ","year":"1987","unstructured":"NZ Shor , An approach to obtaining global extremums in polynomial mathematical programming problems , Cybernetics and Systems Analysis 23 ( 1987 ), no. 5 , 695--700. NZ Shor, An approach to obtaining global extremums in polynomial mathematical programming problems, Cybernetics and Systems Analysis 23 (1987), no. 5, 695--700.","journal-title":"Cybernetics and Systems Analysis"},{"key":"e_1_3_2_1_36_1","volume-title":"Journal of Machine Learning Research - Proceedings Track 23","author":"Spielman Daniel A.","year":"2012","unstructured":"Daniel A. Spielman , Huan Wang , and John Wright , Exact recovery of sparsely-used dictionaries , Journal of Machine Learning Research - Proceedings Track 23 ( 2012 ), 37.1--37.18. Daniel A. Spielman, Huan Wang, and John Wright, Exact recovery of sparsely-used dictionaries, Journal of Machine Learning Research - Proceedings Track 23 (2012), 37.1--37.18."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289464"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587504"}],"event":{"name":"STOC '15: Symposium on Theory of Computing","location":"Portland Oregon USA","acronym":"STOC '15","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-seventh annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2746539.2746605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:00Z","timestamp":1750227420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,14]]},"references-count":37,"alternative-id":["10.1145\/2746539.2746605","10.1145\/2746539"],"URL":"https:\/\/doi.org\/10.1145\/2746539.2746605","relation":{},"subject":[],"published":{"date-parts":[[2015,6,14]]},"assertion":[{"value":"2015-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}