{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:32:08Z","timestamp":1772296328188,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T00:00:00Z","timestamp":1286841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2011,3]]},"DOI":"10.1007\/s10107-010-0422-2","type":"journal-article","created":{"date-parts":[[2010,10,13]],"date-time":"2010-10-13T13:41:56Z","timestamp":1286977316000},"page":"175-202","source":"Crossref","is-referenced-by-count":85,"title":["Null space conditions and thresholds for rank minimization"],"prefix":"10.1007","volume":"127","author":[{"given":"Benjamin","family":"Recht","sequence":"first","affiliation":[]},{"given":"Weiyu","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Babak","family":"Hassibi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,10,12]]},"reference":[{"key":"422_CR1","unstructured":"Ames, B.P.W., Vavasis, S.A.: Nuclear norm minimization for the planted clique and biclique problems (2009). Submitted to Mathematical Programming. Preprint available at http:\/\/arxiv.org\/abs\/0901.3348v1"},{"key":"422_CR2","doi-asserted-by":"crossref","unstructured":"Amit, Y., Fink, M., Srebro, N., Ullman, S.: Uncovering shared structures in multiclass classification. In: Proceedings of the International Conference of Machine Learning (2007)","DOI":"10.1145\/1273496.1273499"},{"key":"422_CR3","unstructured":"Argyriou, A., Micchelli, C.A., Pontil, M.: Convex multi-task feature learning. Machine Learning (2008). Published online first at http:\/\/www.springerlink.com\/"},{"issue":"3","key":"422_CR4","first-page":"611","volume":"9","author":"Z.D. Bai","year":"1999","unstructured":"Bai Z.D.: Methodologies in spectral analysis of large dimensional random matrices. Statistica Sinica 9(3), 611\u2013661 (1999)","journal-title":"Statistica Sinica"},{"key":"422_CR5","unstructured":"Baraniuk, R., Davenport, M., DeVore, R., Wakin, M.: A simple proof of the restricted isometry property for random matrices. Constructive Approximation (2008). To Appear. Preprint available at http:\/\/dsp.rice.edu\/cs\/jlcs-v03.pdf"},{"key":"422_CR6","doi-asserted-by":"crossref","unstructured":"Beck, C., D\u2019Andrea, R.: Computational study and comparisons of LFT reducibility methods. In: Proceedings of the American Control Conference (1998)","DOI":"10.1109\/ACC.1998.703562"},{"issue":"4","key":"422_CR7","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1137\/080738970","volume":"20","author":"J.F. Cai","year":"2008","unstructured":"Cai J.F., Cand\u00e8s E.J., Shen Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956\u20131982 (2008)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"422_CR8","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"E. Cand\u00e8s","year":"2009","unstructured":"Cand\u00e8s E., Recht B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717\u2013772 (2009)","journal-title":"Found. Comput. Math."},{"issue":"2","key":"422_CR9","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E.J. Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s E.J., Romberg J., Tao T.: 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":"422_CR10","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E.J. Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s E.J., Tao T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"422_CR11","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1007\/s00454-005-1220-0","volume":"35","author":"D. Donoho","year":"2006","unstructured":"Donoho D.: High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discret. Comput. Geom. 35(4), 617\u2013652 (2006)","journal-title":"Discret. Comput. Geom."},{"issue":"7","key":"422_CR12","doi-asserted-by":"crossref","first-page":"2845","DOI":"10.1109\/18.959265","volume":"47","author":"D. Donoho","year":"2001","unstructured":"Donoho D., Huo X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47(7), 2845\u20132862 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"27","key":"422_CR13","doi-asserted-by":"crossref","first-page":"9452","DOI":"10.1073\/pnas.0502258102","volume":"102","author":"D.L. Donoho","year":"2005","unstructured":"Donoho D.L., Tanner J.: Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci. USA 102(27), 9452\u20139457 (2005)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"27","key":"422_CR14","doi-asserted-by":"crossref","first-page":"9446","DOI":"10.1073\/pnas.0502269102","volume":"102","author":"D.L. Donoho","year":"2005","unstructured":"Donoho D.L., Tanner J.: Sparse nonnegative solution of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. USA 102(27), 9446\u20139451 (2005)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"422_CR15","unstructured":"Fazel, M.: Matrix Rank Minimization with Applications. Ph.D. thesis, Stanford University (2002)"},{"key":"422_CR16","doi-asserted-by":"crossref","unstructured":"Fazel, M., Hindi, H., Boyd, S.: A rank minimization heuristic with application to minimum order system approximation. In: Proceedings of the American Control Conference (2001)","DOI":"10.1109\/ACC.2001.945730"},{"key":"422_CR17","unstructured":"El Ghaoui, L., Gahinet, P.: Rank minimization under LMI constraints: a framework for output feedback problems. In: Proceedings of the European Control Conference (1993)"},{"key":"422_CR18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02759761","volume":"50","author":"Y. Gordon","year":"1985","unstructured":"Gordon Y.: Some inequalities for Gaussian processes and applications. Israel J. Math. 50, 265\u2013289 (1985)","journal-title":"Israel J. Math."},{"key":"422_CR19","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1214\/aop\/1176991893","volume":"16","author":"Y. Gordon","year":"1988","unstructured":"Gordon Y.: Gaussian processes and almost spherical sections of convex bodies. Ann. Probab. 16, 180\u2013188 (1988)","journal-title":"Ann. Probab."},{"key":"422_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20212-4","volume-title":"Probability in Banach Spaces","author":"M. Ledoux","year":"1991","unstructured":"Ledoux M., Talagrand M.: Probability in Banach Spaces. Springer, Berlin (1991)"},{"key":"422_CR21","doi-asserted-by":"crossref","unstructured":"Lee, K., Bresler, Y.: Efficient and guaranteed rank minimization by atomic decomposition. In: IEEE International Symposium on Information Theory (2009)","DOI":"10.1109\/ISIT.2009.5205530"},{"key":"422_CR22","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial N., London E., Rabinovich Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"422_CR23","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/090755436","volume":"31","author":"Z. Liu","year":"2009","unstructured":"Liu Z., Vandenberghe L.: Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31(3), 1235\u20131256 (2009)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"422_CR24","unstructured":"Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization (2008). Preprint available at http:\/\/www.optimization-online.org\/DB_HTML\/2008\/11\/2151.html"},{"key":"422_CR25","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1070\/SM1967v001n04ABEH001994","volume":"1","author":"V.A. Mar\u010denko","year":"1967","unstructured":"Mar\u010denko V.A., Pastur L.A.: Distributions of eigenvalues for some sets of random matrices. Math. USSR-Sbornik 1, 457\u2013483 (1967)","journal-title":"Math. USSR-Sbornik"},{"key":"422_CR26","doi-asserted-by":"crossref","unstructured":"Meka, R., Jain, P., Caramanis, C., Dhillon, I.S.: Rank minimization via online learning. In: Proceedings of the International Conference on Machine Learning (2008)","DOI":"10.1145\/1390156.1390239"},{"issue":"2","key":"422_CR27","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1109\/9.554402","volume":"42","author":"M. Mesbahi","year":"1997","unstructured":"Mesbahi M., Papavassilopoulos G.P.: On the rank minimization problem over a positive semidefinite linear matrix inequality. IEEE Trans. Autom. Control 42(2), 239\u2013243 (1997)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"8","key":"422_CR28","doi-asserted-by":"crossref","first-page":"1558","DOI":"10.1109\/9.871772","volume":"45","author":"P.A. Parrilo","year":"2000","unstructured":"Parrilo P.A., Khatri S.: On cone-invariant linear matrix inequalities. IEEE Trans. Automat. Control 45(8), 1558\u20131563 (2000)","journal-title":"IEEE Trans. Automat. Control"},{"issue":"3","key":"422_CR29","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B. Recht","year":"2010","unstructured":"Recht B., Fazel M., Parrilo P.: Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471\u2013501 (2010)","journal-title":"SIAM Rev."},{"key":"422_CR30","doi-asserted-by":"crossref","unstructured":"Recht, B., Xu, W., Hassibi, B.: Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization. In: Proceedings of the 47th IEEE Conference on Decision and Control (2008)","DOI":"10.1109\/CDC.2008.4739332"},{"key":"422_CR31","doi-asserted-by":"crossref","unstructured":"Rennie, J.D.M., Srebro, N.: Fast maximum margin matrix factorization for collaborative prediction. In: Proceedings of the International Conference of Machine Learning (2005)","DOI":"10.1145\/1102351.1102441"},{"key":"422_CR32","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1002\/j.1538-7305.1962.tb02419.x","volume":"41","author":"D. Slepian","year":"1962","unstructured":"Slepian D.: The one-sided barrier problem for Gaussian noise. Bell Syst. Tech. J. 41, 463\u2013501 (1962)","journal-title":"Bell Syst. Tech. J."},{"key":"422_CR33","doi-asserted-by":"crossref","unstructured":"Stojnic, M., Xu, W., Hassibi, B.: Compressed sensing - probabilistic analysis of a null-space characterization. In: IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) (2008)","DOI":"10.1109\/ICASSP.2008.4518375"},{"key":"422_CR34","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11\u201312","author":"J.F. Sturm","year":"1999","unstructured":"Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11\u201312, 625\u2013653 (1999)","journal-title":"Optim. Methods Softw."},{"key":"422_CR35","unstructured":"Szarek, S.J.: Metric entropy of homogeneous spaces. In: Quantum probability (Gda\u0144sk, 1997), Banach Center Publ., vol. 43, pp. 395\u2013410. Polish Acad. Sci., Warsaw (1998). Preprint available at arXiv:math\/ 9701213v1"},{"issue":"1","key":"422_CR36","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s11263-005-4939-z","volume":"70","author":"K.Q. Weinberger","year":"2006","unstructured":"Weinberger K.Q., Saul L.K.: Unsupervised learning of image manifolds by semidefinite programming. Int. J. Comput. Vis. 70(1), 77\u201390 (2006)","journal-title":"Int. J. Comput. Vis."},{"key":"422_CR37","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1111\/j.1467-9868.2007.00591.x","volume":"69","author":"M. Yuan","year":"2007","unstructured":"Yuan M., Ekici A., Lu Z., Monteiro R.: Dimension reduction and coefficient estimation in multivariate linear regression. J. Roy. Stat. Soc. Ser. B 69, 329\u2013346 (2007)","journal-title":"J. Roy. Stat. Soc. Ser. B"},{"key":"422_CR38","unstructured":"Zhang, Y.: A simple proof for recoverability of \u2113 1 minimization: go over or under? Tech. Rep. TR05-09, Rice CAAM Department (2005)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0422-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-010-0422-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0422-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T12:30:32Z","timestamp":1559737832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-010-0422-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,12]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["422"],"URL":"https:\/\/doi.org\/10.1007\/s10107-010-0422-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,12]]}}}