{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T11:46:18Z","timestamp":1784288778254,"version":"3.55.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-515362"],"award-info":[{"award-number":["CCF-515362"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-08-1-0749"],"award-info":[{"award-number":["N00014-08-1-0749"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>Suppose that one observes an incomplete subset of entries selected from a low-rank matrix. When is it possible to complete the matrix and recover the entries that have not been seen? We demonstrate that in very general settings, one can perfectly recover all of the missing entries from most sufficiently large subsets by solving a convex programming problem that finds the matrix with the minimum nuclear norm agreeing with the observed entries. The techniques used in this analysis draw upon parallels in the field of compressed sensing, demonstrating that objects other than signals and images can be perfectly reconstructed from very limited information.<\/jats:p>","DOI":"10.1145\/2184319.2184343","type":"journal-article","created":{"date-parts":[[2012,5,23]],"date-time":"2012-05-23T15:47:01Z","timestamp":1337788021000},"page":"111-119","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":555,"title":["Exact matrix completion via convex optimization"],"prefix":"10.1145","volume":"55","author":[{"given":"Emmanuel","family":"Cand\u00e8s","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Recht","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, WI"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273499"},{"key":"e_1_2_1_2_1","volume-title":"Neural Information Processing Systems","author":"Argyriou A.","year":"2007","unstructured":"Argyriou , A. , Evgeniou , T. , Pontil , M. Multi-task feature learning . In Neural Information Processing Systems , 2007 . Argyriou, A., Evgeniou, T., Pontil, M. Multi-task feature learning. In Neural Information Processing Systems, 2007."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.1998.703562"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/080738970"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"e_1_2_1_6_1","first-page":"6","article-title":"Matrix completion with noise","volume":"98","author":"Cand\u00e8s E.J.","year":"2009","unstructured":"Cand\u00e8s , E.J. , Plan , Y . Matrix completion with noise . Proc. IEEE 98 , 6 ( 2009 ), 925--936. Cand\u00e8s, E.J., Plan, Y. Matrix completion with noise. Proc. IEEE 98, 6 (2009), 925--936.","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/23\/3\/008"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"e_1_2_1_10_1","volume-title":"Latent variable graphical model selection via convex optimization. Submitted for publication. Preprint","author":"Chandrasekaran V.","year":"2010","unstructured":"Chandrasekaran , V. , Parrilo , P.A. , Willsky , A.S. Latent variable graphical model selection via convex optimization. Submitted for publication. Preprint available at http:\/\/ssg.mit.edu\/~venkatc\/cpw_lgm_preprint10.pdf, 2010 . Chandrasekaran, V., Parrilo, P.A., Willsky, A.S. Latent variable graphical model selection via convex optimization. Submitted for publication. Preprint available at http:\/\/ssg.mit.edu\/~venkatc\/cpw_lgm_preprint10.pdf, 2010."},{"key":"e_1_2_1_11_1","volume-title":"The convex geometry of linear inverse problems. Submitted for publication. Preprint available at arxiv.org\/1012.0621","author":"Chandrasekaran V.","year":"2010","unstructured":"Chandrasekaran , V. , Recht , B. , Parrilo , P.A. , Willsky , A. The convex geometry of linear inverse problems. Submitted for publication. Preprint available at arxiv.org\/1012.0621 , 2010 . Chandrasekaran, V., Recht, B., Parrilo, P.A., Willsky, A. The convex geometry of linear inverse problems. Submitted for publication. Preprint available at arxiv.org\/1012.0621, 2010."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/090761793"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_2_1_16_1","volume-title":"December","author":"Funk S.","year":"2006","unstructured":"Funk , S. Netflix update: Try this at home , December 2006 . http:\/\/sifter.org\/~simon\/journal\/20061211.html. Funk, S. Netflix update: Try this at home, December 2006. http:\/\/sifter.org\/~simon\/journal\/20061211.html."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104999"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553434"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"e_1_2_1_22_1","first-page":"2057","article-title":"Matrix completion from noisy entries","volume":"11","author":"Keshavan R.H.","year":"2009","unstructured":"Keshavan , R.H. , Montanari , A. , Oh , S . Matrix completion from noisy entries . J. Mach. Learn. Res. 11 ( 2009 ), 2057 -- 2078 . Keshavan, R.H., Montanari, A., Oh, S. Matrix completion from noisy entries. J. Mach. Learn. Res. 11 (2009), 2057--2078.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_23_1","volume-title":"Nuclear norm penalization and optimal rates for noisy low rank matrix completion. Submitted for publication. Preprint available at arxiv.org\/abs\/1011.6256","author":"Koltchinskii V.","year":"2010","unstructured":"Koltchinskii , V. , Tsybakov , A.B. , Lounici , K. Nuclear norm penalization and optimal rates for noisy low rank matrix completion. Submitted for publication. Preprint available at arxiv.org\/abs\/1011.6256 , 2010 . Koltchinskii, V., Tsybakov, A.B., Lounici, K. Nuclear norm penalization and optimal rates for noisy low rank matrix completion. Submitted for publication. Preprint available at arxiv.org\/abs\/1011.6256, 2010."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.263"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0709640104"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0306-5"},{"key":"e_1_2_1_28_1","volume-title":"Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Submitted for publication. Preprint available at arxiv.org\/abs\/1009.2118","author":"Negahban S.","year":"2010","unstructured":"Negahban , S. , Wainwright , M.J. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Submitted for publication. Preprint available at arxiv.org\/abs\/1009.2118 , 2010 . Negahban, S., Wainwright, M.J. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Submitted for publication. Preprint available at arxiv.org\/abs\/1009.2118, 2010."},{"key":"e_1_2_1_29_1","volume-title":"A simpler approach to matrix completion. J. Mach. Learn. Res. (2009). To Appear","author":"Recht B.","year":"2012","unstructured":"Recht , B. A simpler approach to matrix completion. J. Mach. Learn. Res. (2009). To Appear 2012 . Preprint available at http:\/\/arxiv.org\/abs\/0910.0651. Recht, B. A simpler approach to matrix completion. J. Mach. Learn. Res. (2009). To Appear 2012. Preprint available at http:\/\/arxiv.org\/abs\/0910.0651."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102441"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0040-1"},{"key":"e_1_2_1_33_1","volume-title":"Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Meth. Software 11--12","author":"Sturm J.F.","year":"1999","unstructured":"Sturm , J.F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Meth. Software 11--12 ( 1999 ), 625--653. Sturm, J.F. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Meth. Software 11--12 (1999), 625--653."},{"key":"e_1_2_1_34_1","first-page":"615","article-title":"An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems","volume":"6","author":"Toh K.-C.","year":"2010","unstructured":"Toh , K.-C. , Yun , S . An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems . Pac. J. Math. 6 ( 2010 ), 615 -- 640 . Toh, K.-C., Yun, S. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Math. 6 (2010), 615--640.","journal-title":"Pac. J. Math."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2184319.2184343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2184319.2184343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:10Z","timestamp":1750236550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2184319.2184343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2184319.2184343"],"URL":"https:\/\/doi.org\/10.1145\/2184319.2184343","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}