{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T13:38:20Z","timestamp":1778852300930,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2009,12]]},"DOI":"10.1007\/s10208-009-9045-5","type":"journal-article","created":{"date-parts":[[2009,4,2]],"date-time":"2009-04-02T11:58:44Z","timestamp":1238673524000},"page":"717-772","source":"Crossref","is-referenced-by-count":3410,"title":["Exact Matrix Completion via Convex Optimization"],"prefix":"10.1007","volume":"9","author":[{"given":"Emmanuel J.","family":"Cand\u00e8s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Recht","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,3]]},"reference":[{"key":"9045_CR1","unstructured":"ACM SIGKDD, Netflix, Proceedings of KDD Cup and Workshop (2007). Proceedings available online at http:\/\/www.cs.uic.edu\/~liub\/KDD-cup-2007\/proceedings.html ."},{"key":"9045_CR2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1080\/03081088708817810","volume":"21","author":"T. Ando","year":"1987","unstructured":"T. Ando, R.A. Horn, C.R. Johnson, The singular values of a Hadamard product: A basic inequality, Linear Multilinear Algebra 21, 345\u2013365 (1987).","journal-title":"Linear Multilinear Algebra"},{"key":"9045_CR3","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia, Spectral analysis of data, in Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing (2001).","DOI":"10.1145\/380752.380859"},{"key":"9045_CR4","doi-asserted-by":"crossref","unstructured":"C. Beck, R. D\u2019Andrea, Computational study and comparisons of LFT reducibility methods, in Proceedings of the American Control Conference (1998).","DOI":"10.1109\/ACC.1998.703562"},{"key":"9045_CR5","volume-title":"Convex Analysis and Optimization","author":"D.P. Bertsekas","year":"2003","unstructured":"D.P. Bertsekas, A. Nedic, A.E. Ozdaglar, Convex Analysis and Optimization (Athena Scientific, Belmont, 2003)."},{"key":"9045_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"B. Bollob\u00e1s, Random Graphs, 2nd edn. (Cambridge University Press, Cambridge, 2001).","edition":"2"},{"key":"9045_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00004425","volume":"319","author":"A. Buchholz","year":"2001","unstructured":"A. Buchholz, Operator Khintchine inequality in non-commutative probability, Math. Ann. 319, 1\u201316 (2001).","journal-title":"Math. Ann."},{"key":"9045_CR8","unstructured":"J.-F. Cai, E.J. Cand\u00e8s, Z. Shen, A singular value thresholding algorithm for matrix completion, Technical report (2008). Preprint available at http:\/\/arxiv.org\/abs\/0810.3286 ."},{"issue":"3","key":"9045_CR9","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1088\/0266-5611\/23\/3\/008","volume":"23","author":"E.J. Cand\u00e8s","year":"2007","unstructured":"E.J. Cand\u00e8s, J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Probl. 23(3), 969\u2013985 (2007).","journal-title":"Inverse Probl."},{"issue":"2","key":"9045_CR10","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E.J. Cand\u00e8s","year":"2006","unstructured":"E.J. Cand\u00e8s, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52(2), 489\u2013509 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"9045_CR11","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E.J. Cand\u00e8s","year":"2005","unstructured":"E.J. Cand\u00e8s, T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory 51(12), 4203\u20134215 (2005).","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"9045_CR12","doi-asserted-by":"crossref","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"E.J. Cand\u00e8s","year":"2006","unstructured":"E.J. Cand\u00e8s, T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory 52(12), 5406\u20135425 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9045_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BFb0030287","volume-title":"Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science","author":"A.L. Chistov","year":"1984","unstructured":"A.L. Chistov, D.Yu. Grigoriev, Complexity of quantifier elimination in the theory of algebraically closed fields, in Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 176 (Springer, Berlin, 1984), pp. 17\u201331."},{"issue":"4","key":"9045_CR14","doi-asserted-by":"crossref","first-page":"1877","DOI":"10.1214\/aop\/1176989533","volume":"20","author":"V.H. la Pe\u00f1a de","year":"1992","unstructured":"V.H. de la Pe\u00f1a, Decoupling and Khintchine\u2019s inequalities for U-statistics, Ann. Probab. 20(4), 1877\u20131892 (1992).","journal-title":"Ann. Probab."},{"issue":"2","key":"9045_CR15","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1214\/aop\/1176988291","volume":"23","author":"V.H. la Pe\u00f1a de","year":"1995","unstructured":"V.H. de la Pe\u00f1a, S.J. Montgomery-Smith, Decoupling inequalities for the tail probabilities of multivariate U-statistics, Ann. Probab. 23(2), 806\u2013816 (1995).","journal-title":"Ann. Probab."},{"issue":"4","key":"9045_CR16","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D.L. Donoho","year":"2006","unstructured":"D.L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9045_CR17","doi-asserted-by":"crossref","unstructured":"P. Drineas, M.W. Mahoney, S. Muthukrishnan, Subspace sampling and relative-error matrix approximation: Column-based methods, in Proceedings of the Tenth Annual RANDOM (2006).","DOI":"10.1007\/11830924_30"},{"key":"9045_CR18","doi-asserted-by":"crossref","unstructured":"P. Drineas, M.W. Mahoney, S. Muthukrishnan, Subspace sampling and relative-error matrix approximation: Column-row-based methods, in Proceedings of the Fourteenth Annual ESA (2006).","DOI":"10.1007\/11841036_29"},{"key":"9045_CR19","unstructured":"M. Fazel, Matrix rank minimization with applications, Ph.D. thesis, Stanford University (2002)."},{"key":"9045_CR20","volume-title":"Topics in Matrix Analysis","author":"R.A. Horn","year":"1994","unstructured":"R.A. Horn, C.R. Johnson, Topics in Matrix Analysis (Cambridge University Press, Cambridge, 1994). Corrected reprint of the 1991 original."},{"issue":"3","key":"9045_CR21","doi-asserted-by":"crossref","first-page":"1060","DOI":"10.1214\/009117905000000044","volume":"33","author":"T. Klein","year":"2005","unstructured":"T. Klein, E. Rio, Concentration around the mean for maxima of empirical processes, Ann. Probab. 33(3), 1060\u20131077 (2005).","journal-title":"Ann. Probab."},{"issue":"5","key":"9045_CR22","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1214\/aos\/1015957395","volume":"28","author":"B. Laurent","year":"2000","unstructured":"B. Laurent, P. Massart, Adaptive estimation of a quadratic functional by model selection, Ann. Stat. 28(5), 1302\u20131338 (2000).","journal-title":"Ann. Stat."},{"key":"9045_CR23","volume-title":"The Concentration of Measure Phenomenon","author":"M. Ledoux","year":"2001","unstructured":"M. Ledoux, The Concentration of Measure Phenomenon (AMS, Providence, 2001)."},{"issue":"1\u20132","key":"9045_CR24","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10107-003-0441-3","volume":"97","author":"A.S. Lewis","year":"2003","unstructured":"A.S. Lewis, The mathematics of eigenvalue optimization, Math. Programm. 97(1\u20132), 155\u2013176 (2003).","journal-title":"Math. Programm."},{"key":"9045_CR25","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15, 215\u2013245 (1995).","journal-title":"Combinatorica"},{"issue":"7","key":"9045_CR26","first-page":"289","volume":"303","author":"F. Lust-Picquard","year":"1986","unstructured":"F. Lust-Picquard, In\u00e9galit\u00e9s de Khintchine dans C p (1<p<\u221e), C. R. Acad. Sci. Paris, S\u00e9r.\u00a0I 303(7), 289\u2013292 (1986).","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r.\u00a0I"},{"key":"9045_CR27","unstructured":"S. Ma, D. Goldfarb, L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Technical report (2008)."},{"issue":"2","key":"9045_CR28","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1109\/9.554402","volume":"42","author":"M. Mesbahi","year":"1997","unstructured":"M. Mesbahi, G.P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Automat. Control 42(2), 239\u2013243 (1997).","journal-title":"IEEE Trans. Automat. Control"},{"key":"9045_CR29","unstructured":"B. Recht, M. Fazel, P. Parrilo, Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization, SIAM Rev. (2007, submitted). Preprint available at http:\/\/arxiv.org\/abs\/0706.4138 ."},{"key":"9045_CR30","doi-asserted-by":"crossref","unstructured":"J.D.M. Rennie, N. Srebro, Fast maximum margin matrix factorization for collaborative prediction, in Proceedings of the International Conference of Machine Learning (2005).","DOI":"10.1145\/1102351.1102441"},{"issue":"1","key":"9045_CR31","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1006\/jfan.1998.3384","volume":"164","author":"M. Rudelson","year":"1999","unstructured":"M. Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164(1), 60\u201372 (1999).","journal-title":"J. Funct. Anal."},{"key":"9045_CR32","unstructured":"M. Rudelson, R. Vershynin, Sampling from large matrices: an approach through geometric functional analysis, J. ACM, 54(4), Art. 21, 19 pp. (electronic) (2007)."},{"key":"9045_CR33","unstructured":"A.M.-C. So, Y. Ye, Theory of semidefinite programming for sensor network localization, Math. Program., Ser. B, 109, 2007."},{"key":"9045_CR34","unstructured":"N. Srebro, Learning with matrix factorizations, Ph.D. thesis, Massachusetts Institute of Technology, (2004)."},{"issue":"3","key":"9045_CR35","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s002220050108","volume":"126","author":"M. Talagrand","year":"1996","unstructured":"M. Talagrand, New concentration inequalities in product spaces, Invent. Math. 126(3), 505\u2013563 (1996).","journal-title":"Invent. Math."},{"key":"9045_CR36","unstructured":"K.C. Toh, M.J. Todd, R.H. T\u00fct\u00fcnc\u00fc, SDPT3\u2014a MATLAB software package for semidefinite-quadratic-linear programming. Available from http:\/\/www.math.nus.edu.sg\/~mattohkc\/sdpt3.html ."},{"issue":"1","key":"9045_CR37","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L. Vandenberghe","year":"1996","unstructured":"L. Vandenberghe, S.P. Boyd, Semidefinite programming, SIAM Rev. 38(1), 49\u201395 (1996).","journal-title":"SIAM Rev."},{"key":"9045_CR38","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0024-3795(92)90407-2","volume":"170","author":"G.A. Watson","year":"1992","unstructured":"G.A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl. 170, 33\u201345 (1992).","journal-title":"Linear Algebra Appl."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-009-9045-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T04:17:52Z","timestamp":1558239472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-009-9045-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,3]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9045"],"URL":"https:\/\/doi.org\/10.1007\/s10208-009-9045-5","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,3]]}}}