{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:01:05Z","timestamp":1768705265700,"version":"3.49.0"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:00:00Z","timestamp":1560384000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:00:00Z","timestamp":1560384000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s10208-019-09421-3","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T21:02:30Z","timestamp":1560459750000},"page":"367-421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Certifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering"],"prefix":"10.1007","volume":"20","author":[{"given":"Shuyang","family":"Ling","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Strohmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,13]]},"reference":[{"issue":"1","key":"9421_CR1","first-page":"6446","volume":"18","author":"E Abbe","year":"2017","unstructured":"E. Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446\u20136531, 2017.","journal-title":"The Journal of Machine Learning Research"},{"issue":"1","key":"9421_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","volume":"62","author":"E Abbe","year":"2016","unstructured":"E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471\u2013487, 2016.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9421_CR3","doi-asserted-by":"crossref","unstructured":"N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla. Multisection in the stochastic block model using semidefinite programming. In Compressed Sensing and its Applications, pages 125\u2013162. Springer, 2017.","DOI":"10.1007\/978-3-319-69802-1_4"},{"issue":"2","key":"9421_CR4","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"D. Aloise, A. Deshpande, P. Hansen, and P. Popat. NP-hardness of Euclidean sum-of-squares clustering. Machine learning, 75(2):245\u2013248, 2009.","journal-title":"Machine learning"},{"issue":"1","key":"9421_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1214\/17-AOS1545","volume":"46","author":"AA Amini","year":"2018","unstructured":"A. A. Amini and E. Levina. On semidefinite relaxations for the block model. The Annals of Statistics, 46(1):149\u2013179, 2018.","journal-title":"The Annals of Statistics"},{"issue":"2","key":"9421_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):5, 2009.","journal-title":"Journal of the ACM (JACM)"},{"key":"9421_CR7","unstructured":"D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1027\u20131035. Society for Industrial and Applied Mathematics, 2007."},{"key":"9421_CR8","doi-asserted-by":"crossref","unstructured":"P. Awasthi, A. S. Bandeira, M. Charikar, R. Krishnaswamy, S. Villar, and R. Ward. Relax, no need to round: Integrality of clustering formulations. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 191\u2013200. ACM, 2015.","DOI":"10.1145\/2688073.2688116"},{"key":"9421_CR9","doi-asserted-by":"crossref","unstructured":"P. Awasthi and O. Sheffet. Improved spectral-norm bounds for clustering. In APPROX-RANDOM, pages 37\u201349. Springer, 2012.","DOI":"10.1007\/978-3-642-32512-0_4"},{"key":"9421_CR10","doi-asserted-by":"crossref","unstructured":"A. S. Bandeira. Random laplacian matrices and convex relaxations. Foundations of Computational Mathematics, 18(2):345\u2013379, Apr 2018.","DOI":"10.1007\/s10208-016-9341-9"},{"key":"9421_CR11","doi-asserted-by":"crossref","unstructured":"M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems, pages 585\u2013591, 2002.","DOI":"10.7551\/mitpress\/1120.003.0080"},{"issue":"6","key":"9421_CR12","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1162\/089976603321780317","volume":"15","author":"M Belkin","year":"2003","unstructured":"M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373\u20131396, 2003.","journal-title":"Neural Computation"},{"key":"9421_CR13","doi-asserted-by":"crossref","unstructured":"M. Belkin and P. Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. In International Conference on Computational Learning Theory, pages 486\u2013500. Springer, 2005.","DOI":"10.1007\/11503415_33"},{"key":"9421_CR14","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, 2001.","DOI":"10.1137\/1.9780898718829"},{"key":"9421_CR15","doi-asserted-by":"crossref","unstructured":"J. A. Bondy, U. S. R. Murty, et al. Graph Theory with Applications, volume 290. Macmillan London, 1976.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"9421_CR16","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"9421_CR17","doi-asserted-by":"crossref","unstructured":"A. E. Brouwer and W. H. Haemers. Spectra of Graphs. Springer Science+Business Media, 2011.","DOI":"10.1007\/978-1-4614-1939-6"},{"key":"9421_CR18","unstructured":"F. R. Chung. Spectral Graph Theory, volume 92. American Mathematical Society, 1997."},{"issue":"1","key":"9421_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.acha.2006.04.006","volume":"21","author":"RR Coifman","year":"2006","unstructured":"R. R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5\u201330, 2006.","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"21","key":"9421_CR20","doi-asserted-by":"publisher","first-page":"7426","DOI":"10.1073\/pnas.0500334102","volume":"102","author":"RR Coifman","year":"2005","unstructured":"R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the National Academy of Sciences of the United States of America, 102(21):7426\u20137431, 2005.","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"issue":"1","key":"9421_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0707001","volume":"7","author":"C Davis","year":"1970","unstructured":"C. Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1\u201346, 1970.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"9421_CR22","doi-asserted-by":"crossref","unstructured":"I. S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 551\u2013556. ACM, 2004.","DOI":"10.1145\/1014052.1014118"},{"key":"9421_CR23","doi-asserted-by":"crossref","unstructured":"M. P. Do Carmo. Riemannian Geometry. Birkhauser, 1992.","DOI":"10.1007\/978-1-4757-2201-7"},{"key":"9421_CR24","unstructured":"G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 3rd edition, 1996."},{"key":"9421_CR25","doi-asserted-by":"crossref","unstructured":"T. H. Gr\u00f6nwall. Note on the derivatives with respect to a parameter of the solutions of a system of differential equations. Annals of Mathematics, pages 292\u2013296, 1919.","DOI":"10.2307\/1967124"},{"issue":"9","key":"9421_CR26","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1109\/43.159993","volume":"11","author":"L Hagen","year":"1992","unstructured":"L. Hagen and A. B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(9):1074\u20131085, 1992.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"9421_CR27","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and J. Friedman. Unsupervised learning. In The Elements of Statistical Learning, pages 485\u2013585. Springer, 2009.","DOI":"10.1007\/978-0-387-84858-7_14"},{"issue":"2","key":"9421_CR28","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s10107-016-1097-0","volume":"165","author":"T Iguchi","year":"2017","unstructured":"T. Iguchi, D. G. Mixon, J. Peterson, and S. Villar. Probably certifiably correct k-means clustering. Mathematical Programming, 165(2):605\u2013642, 2017.","journal-title":"Mathematical Programming"},{"issue":"8","key":"9421_CR29","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"AK Jain","year":"2010","unstructured":"A. K. Jain. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31(8):651\u2013666, 2010.","journal-title":"Pattern Recognition Letters"},{"key":"9421_CR30","doi-asserted-by":"crossref","unstructured":"A. Kumar and R. Kannan. Clustering with spectral norm and the k-means algorithm. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 299\u2013308. IEEE, 2010.","DOI":"10.1109\/FOCS.2010.35"},{"issue":"1","key":"9421_CR31","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1214\/14-AOS1274","volume":"43","author":"J Lei","year":"2015","unstructured":"J. Lei and A. Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1):215\u2013237, 2015.","journal-title":"The Annals of Statistics"},{"key":"9421_CR32","doi-asserted-by":"crossref","unstructured":"D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times, volume 107. American Mathematical Society, 2017.","DOI":"10.1090\/mbk\/107"},{"key":"9421_CR33","doi-asserted-by":"crossref","unstructured":"X. Li, Y. Li, S. Ling, T. Strohmer, and K. Wei. When do birds of a feather flock together? k-means, proximity, and conic programming. Mathematical Programming, pages 1\u201347, 2018.","DOI":"10.1007\/s10107-018-1333-x"},{"issue":"2","key":"9421_CR34","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129\u2013137, 1982.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9421_CR35","doi-asserted-by":"crossref","unstructured":"M. Mahajan, P. Nimbhorkar, and K. Varadarajan. The planar k-means problem is NP-hard. In International Workshop on Algorithms and Computation, pages 274\u2013285. Springer, 2009.","DOI":"10.1007\/978-3-642-00202-1_24"},{"issue":"4","key":"9421_CR36","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1093\/imaiai\/iax001","volume":"6","author":"DG Mixon","year":"2017","unstructured":"D. G. Mixon, S. Villar, and R. Ward. Clustering subgaussian mixtures by semidefinite programming. Information and Inference: A Journal of the IMA, 6(4):389\u2013415, 2017.","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"9421_CR37","unstructured":"A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems, pages 849\u2013856, 2002."},{"issue":"1","key":"9421_CR38","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/050641983","volume":"18","author":"J Peng","year":"2007","unstructured":"J. Peng and Y. Wei. Approximating k-means-type clustering via semidefinite programming. SIAM Journal on Optimization, 18(1):186\u2013205, 2007.","journal-title":"SIAM Journal on Optimization"},{"key":"9421_CR39","doi-asserted-by":"crossref","unstructured":"K. Rohe, S. Chatterjee, and B. Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, pages 1878\u20131915, 2011.","DOI":"10.1214\/11-AOS887"},{"issue":"8","key":"9421_CR40","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888\u2013905, 2000.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"9421_CR41","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.acha.2006.03.004","volume":"21","author":"A Singer","year":"2006","unstructured":"A. Singer. From graph to manifold Laplacian: The convergence rate. Applied and Computational Harmonic Analysis, 21(1):128\u2013134, 2006.","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"1","key":"9421_CR42","first-page":"58","volume":"6","author":"A Singer","year":"2016","unstructured":"A. Singer and H.-T. Wu. Spectral convergence of the connection Laplacian from random samples. Information and Inference: A Journal of the IMA, 6(1):58\u2013123, 2016.","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"9421_CR43","unstructured":"G. W. Stewart. Perturbation theory for the singular value decomposition. Technical Report CS-TR-2539, University of Maryland, Sep 1990."},{"issue":"1","key":"9421_CR44","first-page":"3208","volume":"19","author":"M Tepper","year":"2018","unstructured":"M. Tepper, A. M. Sengupta, and D. Chklovskii. Clustering is semidefinitely not that hard: Nonnegative sdp for manifold disentangling. The Journal of Machine Learning Research, 19(1):3208\u20133237, 2018.","journal-title":"The Journal of Machine Learning Research"},{"key":"9421_CR45","unstructured":"N. G. Trillos, M. Gerlach, M. Hein, and D. Slepcev. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace-Beltrami operator. arXiv preprint arXiv:1801.10108 , 2018."},{"issue":"2","key":"9421_CR46","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.acha.2016.09.003","volume":"45","author":"NG Trillos","year":"2018","unstructured":"N. G. Trillos and D. Slep\u010dev. A variational approach to the consistency of spectral clustering. Applied and Computational Harmonic Analysis, 45(2):239\u2013281, 2018.","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"4","key":"9421_CR47","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","volume":"12","author":"JA Tropp","year":"2012","unstructured":"J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389\u2013434, 2012.","journal-title":"Foundations of Computational Mathematics"},{"key":"9421_CR48","doi-asserted-by":"crossref","unstructured":"R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Y. C. Eldar and G. Kutyniok, editors, Compressed Sensing: Theory and Applications, chapter 5. Cambridge University Press, 2012.","DOI":"10.1017\/CBO9780511794308.006"},{"issue":"4","key":"9421_CR49","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Von Luxburg","year":"2007","unstructured":"U. Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395\u2013416, 2007.","journal-title":"Statistics and Computing"},{"key":"9421_CR50","doi-asserted-by":"crossref","unstructured":"U. Von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. The Annals of Statistics, pages 555\u2013586, 2008.","DOI":"10.1214\/009053607000000640"},{"key":"9421_CR51","doi-asserted-by":"crossref","unstructured":"D. Wagner and F. Wagner. Between min cut and graph bisection. In International Symposium on Mathematical Foundations of Computer Science, pages 744\u2013750. Springer, 1993.","DOI":"10.1007\/3-540-57182-5_65"},{"key":"9421_CR52","doi-asserted-by":"crossref","unstructured":"W. Walter. Ordinary Differential Equations, volume 1(182). Springer Science and Media, 1998.","DOI":"10.1007\/978-1-4612-0601-9_1"},{"key":"9421_CR53","unstructured":"E. P. Xing and M. I. Jordan. On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Technical Report UCB\/CSD-03-1265, EECS Department, University of California, Berkeley, Jun 2003."},{"key":"9421_CR54","unstructured":"B. Yan, P. Sarkar, and X. Cheng. Provable estimation of the number of blocks in block models. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1185\u20131194. PMLR, 09\u201311 Apr 2018."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09421-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-019-09421-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09421-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T18:32:22Z","timestamp":1721413942000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-019-09421-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,13]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["9421"],"URL":"https:\/\/doi.org\/10.1007\/s10208-019-09421-3","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,13]]},"assertion":[{"value":"3 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}