{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:50:39Z","timestamp":1773280239775,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"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":[[2012,5,19]]},"DOI":"10.1145\/2213977.2213994","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"145-162","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":155,"title":["Computing a nonnegative matrix factorization -- provably"],"prefix":"10.1145","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[{"name":"Princeton University and Center for Computational Intractability, Princeton, NJ, USA"}]},{"given":"Rong","family":"Ge","sequence":"additional","affiliation":[{"name":"Princeton University and Center for Computational Intractability, Princeton, NJ, USA"}]},{"given":"Ravindran","family":"Kannan","sequence":"additional","affiliation":[{"name":"Microsoft Research India, Bangalore , India"}]},{"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ, USA"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808742"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00142-5"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_3_2_2_4_1","unstructured":"D. Blei. Personal communication.  D. Blei. Personal communication."},{"key":"e_1_3_2_2_5_1","first-page":"993","volume-title":"Journal of Machine Learning Research","author":"Blei D.","year":"2003","unstructured":"D. Blei , A. Ng and M. Jordan . Latent Dirichlet allocation . Journal of Machine Learning Research , pp. 993 -- 1022 , 2003 . Preliminary version in NIPS 2001. D. Blei, A. Ng and M. Jordan. Latent Dirichlet allocation. Journal of Machine Learning Research, pp. 993--1022, 2003. Preliminary version in NIPS 2001."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/265020"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0042-6989(01)00303-0"},{"key":"e_1_3_2_2_8_1","first-page":"149","volume-title":"Nonnegative ranks, decompositions and factorizations of nonnegative matices. Linear Algebra and its Applications","author":"Cohen J.","year":"1993","unstructured":"J. Cohen and U. Rothblum . Nonnegative ranks, decompositions and factorizations of nonnegative matices. Linear Algebra and its Applications , pp. 149 -- 168 , 1993 . J. Cohen and U. Rothblum. Nonnegative ranks, decompositions and factorizations of nonnegative matices. Linear Algebra and its Applications, pp. 149--168, 1993."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9"},{"key":"e_1_3_2_2_10_1","volume-title":"NIPS","author":"Donoho D.","year":"2003","unstructured":"D. Donoho and V. Stodden . When does non-negative matrix factorization give the correct decomposition into parts ? NIPS , 2003 . D. Donoho and V. Stodden. When does non-negative matrix factorization give the correct decomposition into parts? NIPS, 2003."},{"key":"e_1_3_2_2_11_1","volume-title":"Arxiv","author":"Fiorini S.","year":"2011","unstructured":"S. Fiorini , T. Rothvo\u00df and H. Tiwary . Extended formulations for polygons . Arxiv , 2011 . S. Fiorini, T. Rothvo\u00df and H. Tiwary. Extended formulations for polygons. Arxiv, 2011."},{"key":"e_1_3_2_2_12_1","volume-title":"Matrix Computations The Johns Hopkins University Press","author":"Golub G.","year":"1996","unstructured":"G. Golub and C. van Loan . Matrix Computations The Johns Hopkins University Press , 1996 . G. Golub and C. van Loan. Matrix Computations The Johns Hopkins University Press, 1996."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(88)80005-1"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091500011925"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/1527789"},{"key":"e_1_3_2_2_16_1","first-page":"289","article-title":"Probabilistic latent semantic analysis","author":"Hofmann T.","year":"1999","unstructured":"T. Hofmann . Probabilistic latent semantic analysis . UAI , pp. 289 -- 296 , 1999 . T. Hofmann. Probabilistic latent semantic analysis. UAI, pp. 289--296, 1999.","journal-title":"UAI"},{"key":"e_1_3_2_2_17_1","first-page":"1457","volume-title":"Journal of Machine Learning Research","author":"Hoyer P.","year":"2004","unstructured":"P. Hoyer . Non-negative matrix factorization with sparseness constraints . Journal of Machine Learning Research , pp. 1457 -- 1469 , 2004 . P. Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of Machine Learning Research, pp. 1457--1469, 2004."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9263-4"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","DOI":"10.1002\/0471221317","volume-title":"Independent Component Analysis","author":"Hyvarinen A.","year":"2001","unstructured":"A. Hyvarinen , J. Karhunen and E. Oja . Independent Component Analysis . Wiley Interscience , 2001 . A. Hyvarinen, J. Karhunen and E. Oja. Independent Component Analysis. Wiley Interscience, 2001."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.013"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1757"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1971.10488823"},{"key":"e_1_3_2_2_24_1","first-page":"788","volume-title":"Nature","author":"Lee D.","year":"1999","unstructured":"D. Lee and H. Seung . Learning the parts of objects by non-negative matrix factorization . Nature , pp. 788 -- 791 , 1999 . D. Lee and H. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, pp. 788--791, 1999."},{"key":"e_1_3_2_2_25_1","first-page":"556","volume-title":"NIPS","author":"Lee D.","year":"2000","unstructured":"D. Lee and H. Seung . Algorithms for non-negative matrix factorization . NIPS , pp. 556 -- 562 , 2000 . D. Lee and H. Seung. Algorithms for non-negative matrix factorization. NIPS, pp. 556--562, 2000."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90035-U"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"Matousek J.","year":"2002","unstructured":"J. Matousek . Lectures on Discrete Geometry . Springer , 2002 . J. Matousek. Lectures on Discrete Geometry. Springer, 2002."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/env.3170050203"},{"key":"e_1_3_2_2_30_1","first-page":"1065","volume-title":"SODA","author":"Patrascu M.","year":"2010","unstructured":"M. Patrascu and R. Williams . On the possibility of faster SAT algorithms . SODA , pp. 1065 -- 1075 , 2010 . M. Patrascu and R. Williams. On the possibility of faster SAT algorithms. SODA, pp. 1065--1075, 2010."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1711"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969640"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A decision method for elementary algebra and geometry","author":"Tarski A.","year":"1951","unstructured":"A. Tarski . A decision method for elementary algebra and geometry . University of California Press , 1951 . A. Tarski. A decision method for elementary algebra and geometry. University of California Press, 1951."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860485"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958447.1958459"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62232"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213994","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2213994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":37,"alternative-id":["10.1145\/2213977.2213994","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2213994","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}