{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:37:35Z","timestamp":1775183855173,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2013,11,30]],"date-time":"2013-11-30T00:00:00Z","timestamp":1385769600000},"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":[[2014,10]]},"DOI":"10.1007\/s10107-013-0729-x","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T01:37:12Z","timestamp":1385689032000},"page":"429-465","source":"Crossref","is-referenced-by-count":34,"title":["Guaranteed clustering and biclustering via semidefinite programming"],"prefix":"10.1007","volume":"147","author":[{"given":"Brendan P. W.","family":"Ames","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,11,30]]},"reference":[{"key":"729_CR1","unstructured":"Ackerman, M., Ben-David, S.: Clusterability: a theoretical study. In: Proceedings of the AISTATS-09. JMLR: W &CP 5, 1\u20138 (2009)"},{"issue":"2","key":"729_CR2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: Np-hardness of euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"key":"729_CR3","unstructured":"Ames, B., Vavasis, S.: Convex optimization for the planted k-disjoint-clique problem. Arxiv, preprint arXiv:1008.2814, 2010"},{"issue":"1","key":"729_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-011-0460-4","volume":"129","author":"B Ames","year":"2011","unstructured":"Ames, B., Vavasis, S.: Nuclear norm minimization for the planted clique and biclique problems. Math. Program. 129(1), 1\u201321 (2011)","journal-title":"Math. Program."},{"issue":"3","key":"729_CR5","first-page":"954","volume":"25","author":"S Balakrishnan","year":"2011","unstructured":"Balakrishnan, S., Xu, M., Krishnamurthy, A., Singh, A.: Noise thresholds for spectral clustering. Adv. Neural Inf. Process. Syst. 25(3), 954\u2013962 (2011)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"729_CR6","unstructured":"Bansal, N.A., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1), 89\u2013113 (2004)"},{"key":"729_CR7","doi-asserted-by":"crossref","unstructured":"Berkhin, P.: A survey of clustering data mining techniques. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping Multidimensional Data: Recent Advances in Clustering, pp. 25\u201371. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/3-540-28349-8_2"},{"issue":"4","key":"729_CR8","doi-asserted-by":"crossref","first-page":"1196","DOI":"10.1137\/S1052623497330963","volume":"10","author":"E Birgin","year":"2000","unstructured":"Birgin, E., Mart\u00ednez, J., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optimiz. 10(4), 1196\u20131211 (2000)","journal-title":"SIAM J. Optimiz."},{"issue":"1","key":"729_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends. Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends. Mach. Learn."},{"key":"729_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"9","key":"729_CR11","doi-asserted-by":"crossref","first-page":"2964","DOI":"10.1016\/j.cor.2007.01.005","volume":"35","author":"S Busygin","year":"2008","unstructured":"Busygin, S., Prokopyev, O., Pardalos, P.: Biclustering in data mining. Comput. Oper. Res. 35(9), 2964\u20132987 (2008)","journal-title":"Comput. Oper. Res."},{"key":"729_CR12","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E., Plan, Y.: Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements. Arxiv, preprint arXiv:1001.0339 (2010)","DOI":"10.1109\/TIT.2011.2111771"},{"issue":"6","key":"729_CR13","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":"8","key":"729_CR14","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"E Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"12","key":"729_CR15","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"729_CR16","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D Donoho","year":"2006","unstructured":"Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"729_CR17","doi-asserted-by":"crossref","unstructured":"Eckstein, J., Bertsekas, D.P.: On the douglasrachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1\u20133), 293\u2013318 (1992)","DOI":"10.1007\/BF01581204"},{"key":"729_CR18","doi-asserted-by":"crossref","unstructured":"Fan, N., Boyko, N., Pardalos, P.: Recent advances of data biclustering with application in computational neuroscience. Computat. Neurosci. pp. 105\u2013132 (2010)","DOI":"10.1007\/978-0-387-88630-5_6"},{"key":"729_CR19","unstructured":"Fan, N., Pardalos, P.: Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs. J. Comb. Optimiz. 23(2), 224\u2013251 (2012)"},{"key":"729_CR20","unstructured":"Flynn, C., Perry, P.: Consistent biclustering. Arxiv, preprint arXiv:1206.6927 (2012)"},{"issue":"3","key":"729_CR21","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z., Koml\u00f3s, J.: The eigenvalues of random symmetric matrices. Combinatorica 1(3), 233\u2013241 (1981)","journal-title":"Combinatorica"},{"issue":"2","key":"729_CR22","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1214\/aop\/1176994775","volume":"8","author":"S Geman","year":"1980","unstructured":"Geman, S.: A limit theorem for the norm of random matrices. Ann. Prob. 8(2), 252\u2013261 (1980)","journal-title":"Ann. Prob."},{"key":"729_CR23","volume-title":"Matrix Computations","author":"G Van Golub","year":"1996","unstructured":"Golub, G.Van, Loan, C.: Matrix Computations. Johns Hopkins University Press, Baltimore (1996)"},{"issue":"3","key":"729_CR24","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1109\/TIT.2011.2104999","volume":"57","author":"D Gross","year":"2011","unstructured":"Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57(3), 1548\u20131566 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"729_CR25","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1962","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13\u201330 (1962)","journal-title":"J. Am. Stat. Assoc."},{"key":"729_CR26","unstructured":"Jalali, A., Chen, Y., Sanghavi, S., Xu, H.: Clustering partially observed graphs via convex optimization. Arxiv, preprint arXiv:1104.4803 (2011)"},{"issue":"3","key":"729_CR27","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/990308.990313","volume":"51","author":"R Kannan","year":"2004","unstructured":"Kannan, R., Vempala, S., Vetta, A.: On clusterings: good, bad and spectral. J. ACM 51(3), 497\u2013515 (2004)","journal-title":"J. ACM"},{"key":"729_CR28","unstructured":"Kolar, M., Balakrishnan, S., Rinaldo, A., Singh, A.: Minimax localization of structural information in large noisy matrices. In: Shawe-Taylor, J., Zemel, R.S., Bartlett, P. (eds.) Advances in Neural Information Processing Systems, pp. 909\u2013917. FCN, Weinberger (2011)"},{"key":"729_CR29","unstructured":"Lu, Z., Zhang, Y.: Penalty decomposition methods for rank minimization. Technical report. Department of Mathematics, Simon Fraser University. Arxiv, preprint (2010)"},{"key":"729_CR30","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp. 712\u2013728. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.58"},{"key":"729_CR31","first-page":"849","volume":"2","author":"A Ng","year":"2002","unstructured":"Ng, A., Jordan, M., Weiss, Y.: On spectral clustering: analysis and an algorithm. Adv. Neural Inf. Process. Syst. 2, 849\u2013856 (2002)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"729_CR32","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L., Swamy, C.: The effectiveness of Lloyd-type methods for the k-means problem. In: Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"729_CR33","unstructured":"Oymak, S., Hassibi, B.: Finding dense clusters via \u201clow rank + sparse\u201d decomposition. Arxiv, preprint arXiv:1104.5186 (2011)"},{"key":"729_CR34","doi-asserted-by":"crossref","unstructured":"Oymak, S., Mohan, K., Fazel, M., Hassibi, B.: A simplified approach to recovery conditions for low rank matrices. In: Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on IEEE, pp. 2318\u20132322 (2011)","DOI":"10.1109\/ISIT.2011.6033976"},{"issue":"1","key":"729_CR35","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/050641983","volume":"18","author":"J Peng","year":"2007","unstructured":"Peng, J., Wei, Y.: Approximating k-means-type clustering via semidefinite programming. SIAM J. Optimiz. 18(1), 186\u2013205 (2007)","journal-title":"SIAM J. Optimiz."},{"key":"729_CR36","first-page":"3413","volume":"12","author":"B Recht","year":"2011","unstructured":"Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413\u20133430 (2011)","journal-title":"J. Mach. Learn. Res."},{"key":"729_CR37","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 linear matrix equations via muclear norm minimization. SIAM Rev. 52, 471 (2010)","journal-title":"SIAM Rev."},{"key":"729_CR38","doi-asserted-by":"crossref","unstructured":"Recht, B., Xu, W., Hassibi, B.: Null space conditions and thresholds for rank minimization. Mathematical Programming, pp. 1\u201328 (2010)","DOI":"10.1007\/s10107-010-0422-2"},{"key":"729_CR39","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1997","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1997)"},{"issue":"4","key":"729_CR40","doi-asserted-by":"crossref","first-page":"1878","DOI":"10.1214\/11-AOS887","volume":"39","author":"K Rohe","year":"2011","unstructured":"Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Stat. 39(4), 1878\u20131915 (2011)","journal-title":"Ann. Stat."},{"key":"729_CR41","unstructured":"Rohe, K., Yu, B.: Co-clustering for directed graphs; the stochastic co-blockmodel and a spectral algorithm. Arxiv, preprint arXiv:1204.2296 (2012)"},{"key":"729_CR42","first-page":"230","volume":"2002","author":"R Shamir","year":"2002","unstructured":"Shamir, R., Tsur, D.: Improved algorithms for the random cluster graph model. Alg. Theory SWAT 2002, 230\u2013239 (2002)","journal-title":"Alg. Theory SWAT"},{"issue":"1","key":"729_CR43","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s10994-009-5158-y","volume":"79","author":"V Singh","year":"2010","unstructured":"Singh, V., Mukherjee, L., Peng, J., Xu, J.: Ensemble clustering using semidefinite programming with applications. Mach. Learn. 79(1), 177\u2013200 (2010)","journal-title":"Mach. Learn."},{"key":"729_CR44","doi-asserted-by":"crossref","DOI":"10.1090\/fim\/027","volume-title":"Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization","author":"L Tun\u00e7el","year":"2010","unstructured":"Tun\u00e7el, L.: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization. American Mathematical Society, Providence (2010)"},{"issue":"2","key":"729_CR45","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1137\/080714488","volume":"31","author":"E Berg Van Den","year":"2008","unstructured":"Van Den Berg, E., Friedlander, M.: Probing the pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890\u2013912 (2008)","journal-title":"SIAM J. Sci. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0729-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-013-0729-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0729-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T06:42:04Z","timestamp":1564900924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-013-0729-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,30]]},"references-count":45,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["729"],"URL":"https:\/\/doi.org\/10.1007\/s10107-013-0729-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,30]]}}}