{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:47:21Z","timestamp":1779295641773,"version":"3.51.4"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,4,14]],"date-time":"2021-04-14T00:00:00Z","timestamp":1618358400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,14]],"date-time":"2021-04-14T00:00:00Z","timestamp":1618358400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["15K20986"],"award-info":[{"award-number":["15K20986"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["26242027"],"award-info":[{"award-number":["26242027"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s10994-020-05940-1","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T06:31:42Z","timestamp":1618468302000},"page":"933-964","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Convex programming based spectral clustering"],"prefix":"10.1007","volume":"110","author":[{"given":"Tomohiko","family":"Mizutani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,14]]},"reference":[{"key":"5940_CR1","doi-asserted-by":"publisher","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. (2009). NP-hardness of Euclidean sum-of-squares clustering. Machine Learning, 75, 245\u2013248.","journal-title":"Machine Learning"},{"issue":"2","key":"5940_CR2","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0169-7439(01)00119-8","volume":"57","author":"UMC Ara\u00fajo","year":"2001","unstructured":"Ara\u00fajo, U. M. C., Saldanha, B. T. C., Galv\u00e3o, R. K. H., Yoneyama, T., Chame, H. C., & Visani, V. (2001). The successive projections algorithm for variable selection in spectroscopic multicomponent analysis. Chemometrics and Intelligent Laboratory Systems, 57(2), 65\u201373.","journal-title":"Chemometrics and Intelligent Laboratory Systems"},{"key":"5940_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R., Kannan, R., & Moitra, A. (2012). Computing a nonnegative matrix factorization\u2014provably. In: Proceedings of the 44th symposium on theory of computing (STOC) (pp. 145\u2013162).","DOI":"10.1145\/2213977.2213994"},{"issue":"2","key":"5940_CR4","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., & Vazirani, U. (2009). Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56(2), 5:1\u20135:37.","journal-title":"Journal of the ACM"},{"key":"5940_CR5","unstructured":"Arthur, D., & Vassilvitskii, S. (2007). $$k$$-means++: The advantages of careful seeding. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 1027\u20131035)."},{"key":"5940_CR6","unstructured":"Bach, F.\u00a0R., & Jordan, M.\u00a0I. (2003). Learning spectral clustering. In: Advances in neural information processing systems 16 (NIPS) (pp. 305\u2013312)."},{"issue":"8","key":"5940_CR7","doi-asserted-by":"publisher","first-page":"1548","DOI":"10.1109\/TPAMI.2010.231","volume":"33","author":"D Cai","year":"2011","unstructured":"Cai, D., He, X., Han, J., & Huang, T. S. (2011). Graph regularized nonnegative matrix factorization for data representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8), 1548\u20131560.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"5940_CR8","unstructured":"Chen, X., & Cai, D. (2011). Large scale spectral clustering with landmark-based representation. In: Proceedings of the 25th AAAI conference on artificial intelligence (pp. 313\u2013318)."},{"key":"5940_CR9","volume-title":"Spectral graph theory","author":"FRK Chung","year":"1997","unstructured":"Chung, F. R. K. (1997). Spectral graph theory. American Mathematical Society."},{"key":"5940_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, G., Afshar, S., Tapson, J., & van Schaik, A. (2017). EMNIST: An extension of MNIST to handwritten letters. arXiv:1702.05373.","DOI":"10.1109\/IJCNN.2017.7966217"},{"key":"5940_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.comgeo.2018.09.001","volume":"76","author":"TK Dey","year":"2019","unstructured":"Dey, T. K., Peng, P., Rossi, A., & Sidiropoulos, A. (2019). Spectral concentration and greedy $$k$$-clustering. Computational Geometry: Theory and Applications, 76, 19\u201332.","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"5","key":"5940_CR12","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1147\/rd.175.0420","volume":"17","author":"WE Donath","year":"1973","unstructured":"Donath, W. E., & Hoffman, A. J. (1973). Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 17(5), 420\u2013425.","journal-title":"IBM Journal of Research and Development"},{"key":"5940_CR13","unstructured":"Donoho, D., & Stodden, V. (2003). When does non-negative matrix factorization give a correct decomposition into parts? In: Proceedings of advances in neural information processing systems 16 (NIPS) (pp. 1141\u20131148)."},{"issue":"2","key":"5940_CR14","doi-asserted-by":"publisher","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298\u2013305.","journal-title":"Czechoslovak Mathematical Journal"},{"key":"5940_CR15","doi-asserted-by":"crossref","unstructured":"Gharan, S.\u00a0O., & Trevisan, L. (2014). Partitioning into expanders. In: Proceedings of the 25 annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 1256\u20131266).","DOI":"10.1137\/1.9781611973402.93"},{"issue":"2","key":"5940_CR16","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1137\/130946782","volume":"7","author":"N Gillis","year":"2014","unstructured":"Gillis, N. (2014). Successive nonnegative projection algorithm for robust nonnegative blind source separation. SIAM Journal of Imaging Science, 7(2), 1420\u20131450.","journal-title":"SIAM Journal of Imaging Science"},{"issue":"4","key":"5940_CR17","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1109\/TPAMI.2013.226","volume":"36","author":"N Gillis","year":"2014","unstructured":"Gillis, N., & Vavasis, S. A. (2014). Fast and robust recursive algorithms for separable nonnegative matrix factorization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(4), 698\u2013714.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"5940_CR18","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix computation","author":"GH Golub","year":"2013","unstructured":"Golub, G. H., & Loan, C. F. V. (2013). Matrix computation (4th ed.). The Johns Hopkins University Press.","edition":"4"},{"issue":"6","key":"5940_CR19","doi-asserted-by":"publisher","first-page":"1212","DOI":"10.1109\/TKDE.2019.2903410","volume":"32","author":"D Huang","year":"2020","unstructured":"Huang, D., Wang, C.-D., Wu, J.-S., Lai, J.-H., & Kwoh, C.-K. (2020). Ultra-scalable spectral clustering and ensemble clustering. IEEE Transactions on Knowledge and Data Engineering, 32(6), 1212\u20131226.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"3","key":"5940_CR20","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1145\/990308.990313","volume":"51","author":"R Kannan","year":"2004","unstructured":"Kannan, R., Vempala, S., & Vetta, A. (2004). On clusterings: Good, bad and spectral. Journal of the ACM, 51(3), 497\u2013515.","journal-title":"Journal of the ACM"},{"issue":"2","key":"5940_CR21","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1287\/moor.21.2.307","volume":"21","author":"LG Khachiyan","year":"1996","unstructured":"Khachiyan, L. G. (1996). Rounding of polytopes in the real number model of computation. Mathematics of Operations Research, 21(2), 307\u2013320.","journal-title":"Mathematics of Operations Research"},{"key":"5940_CR22","doi-asserted-by":"crossref","unstructured":"Kolev, P., & Mehlhorn, K. (2016). A note on spectral clustering. In: 24th annual European symposium on algorithms (ESA 2016) (Vol. 57, pp. 57:1\u201357:14).","DOI":"10.1007\/978-3-662-43978-4_4496"},{"key":"5940_CR23","unstructured":"Kolev, P., & Mehlhorn, K. (2018). Approximate spectral clustering: Efficiency and guarantees. arXiv:1509.09188v5."},{"issue":"1","key":"5940_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10957-005-2653-6","volume":"126","author":"P Kumar","year":"2005","unstructured":"Kumar, P., & Yildirim, E. A. (2005). Minimum-volume enclosing ellipsoids and core sets. Journal of Optimization Theory and Applications, 126(1), 1\u201321.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"5940_CR25","doi-asserted-by":"crossref","unstructured":"Kwok, T.\u00a0C., Lau, L.\u00a0C., Lee, Y.\u00a0T., Gharan, S.\u00a0O., & Trevisan, L. (2013). Improved cheeger\u2019s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In: Proceedings of the 45th annual ACM symposium on theory of computing (STOC) (pp. 11\u201320).","DOI":"10.1145\/2488608.2488611"},{"issue":"11","key":"5940_CR26","doi-asserted-by":"publisher","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y Lecun","year":"1998","unstructured":"Lecun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11), 2278\u20132324.","journal-title":"Proceedings of the IEEE"},{"key":"5940_CR27","doi-asserted-by":"crossref","unstructured":"Lee, J.\u00a0R., Gharan, S.\u00a0O., & Trevisan, L. (2012). Multi-way spectral partitioning and higher-order cheeger inequalities. In: Proceedings of the 44th annual ACM symposium on theory of computing (STOC) (pp. 1117\u20131130).","DOI":"10.1145\/2213977.2214078"},{"issue":"1","key":"5940_CR28","first-page":"215","volume":"43","author":"J Lei","year":"2015","unstructured":"Lei, J., & Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 215\u2013237.","journal-title":"The Annals of Statistics"},{"issue":"2","key":"5940_CR29","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129\u2013137.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5940_CR30","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Nimbhorkar, P., & Varadarajan, K. (2009). The planar $$k$$-means problem is NP-hard. In: Proceedings of the 3rd international workshop on algorithms and computation (WALCOM) (pp. 274\u2013285).","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"5940_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to information retrieval","author":"CD Manning","year":"2008","unstructured":"Manning, C. D., Raghavan, P., & Schuetze, H. (2008). Introduction to information retrieval. Cambridge University Press."},{"issue":"1\u20132","key":"5940_CR32","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0166-218X(90)90133-W","volume":"27","author":"DW Matula","year":"1990","unstructured":"Matula, D. W., & Shahrokhi, F. (1990). Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics, 27(1\u20132), 113\u2013123.","journal-title":"Discrete Applied Mathematics"},{"key":"5940_CR33","doi-asserted-by":"crossref","unstructured":"McSherry, F. (2001). Spectral partitioning of random graphs. In: Proceedings of the 42nd IEEE symposium on foundations of computer science (FOCS) (pp. 529\u2013537).","DOI":"10.1109\/SFCS.2001.959929"},{"key":"5940_CR34","first-page":"1011","volume":"15","author":"T Mizutani","year":"2014","unstructured":"Mizutani, T. (2014). Ellipsoidal rounding for nonnegative matrix factorization under noisy separability. Journal of Machine Learning Research, 15, 1011\u20131039.","journal-title":"Journal of Machine Learning Research"},{"key":"5940_CR35","unstructured":"Mizutani, T. (2015). Spectral clustering by ellipsoid and its connection to separable nonnegative matrix factorization. arXiv:1503.01531."},{"key":"5940_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-020-01639-3","author":"T Mizutani","year":"2020","unstructured":"Mizutani, T. (2020). Improved analysis of spectral algorithm for clustering. Optimization Letters. https:\/\/doi.org\/10.1007\/s11590-020-01639-3.","journal-title":"Optimization Letters"},{"key":"5940_CR37","unstructured":"Ng, A.\u00a0Y., Jordan, M., & Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. In: Advances in neural information processing systems 14 (NIPS) (pp. 849\u2013856)."},{"key":"5940_CR38","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L. J., & Swamy, C. (2012). The effectiveness of Lloyd-type methods for the $$k$$-means problem. Journal of the ACM, 59(6).","DOI":"10.1145\/2395116.2395117"},{"key":"5940_CR39","unstructured":"Peng, R., Sun, H., & Zanetti, L. (2015). Partitioning well-clustered graphs: Spectral clustering works! In: Proceedings of the 28th conference on learning theory (COLT) (Vol. 40, pp. 1423\u20131455)."},{"issue":"2","key":"5940_CR40","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1137\/15M1047209","volume":"46","author":"R Peng","year":"2017","unstructured":"Peng, R., Sun, H., & Zanetti, L. (2017). Partitioning well-clustered graphs: Spectral clustering works!. SIAM Journal on Computing, 46(2), 710\u2013743.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"5940_CR41","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1214\/11-AOS887","volume":"39","author":"K Rohe","year":"2011","unstructured":"Rohe, K., Chatterjee, S., & Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4), 596\u2013616.","journal-title":"The Annals of Statistics"},{"issue":"8","key":"5940_CR42","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888\u2013905.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"5940_CR43","doi-asserted-by":"crossref","unstructured":"Sinop, A.\u00a0K. (2016). How to round subspaces: A new spectral clustering algorithm. In: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 1832\u20131847).","DOI":"10.1137\/1.9781611974331.ch128"},{"key":"5940_CR44","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1080\/10556789908805762","volume":"11","author":"K-C Toh","year":"1999","unstructured":"Toh, K.-C., Todd, M. J., & T\u00fct\u00fcnc\u00fc, R. H. (1999). SDPT3\u2013A MATLAB software package for semidefinite programming. Optimization Methods and Software, 11, 545\u2013581.","journal-title":"Optimization Methods and Software"},{"issue":"4","key":"5940_CR45","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U von Luxburg","year":"2007","unstructured":"von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395\u2013416.","journal-title":"Statistics and Computing"},{"key":"5940_CR46","unstructured":"Xiao, H., Rasul, K., & Vollgraf, R. (2017). Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. arXiv:1708.07747."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-020-05940-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-020-05940-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-020-05940-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T09:44:41Z","timestamp":1671875081000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-020-05940-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,14]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["5940"],"URL":"https:\/\/doi.org\/10.1007\/s10994-020-05940-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,14]]},"assertion":[{"value":"10 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}