{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T16:00:17Z","timestamp":1774281617328,"version":"3.50.1"},"reference-count":70,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000121","name":"NSF CAREER Award","doi-asserted-by":"publisher","award":["DMS-1752614"],"award-info":[{"award-number":["DMS-1752614"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"name":"UIUC Research Board Award","award":["RB18099"],"award-info":[{"award-number":["RB18099"]}]},{"name":"Simons Fellowship"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DMS-1907316"],"award-info":[{"award-number":["DMS-1907316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1109\/tit.2021.3063155","type":"journal-article","created":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T21:23:03Z","timestamp":1614720183000},"page":"4223-4238","source":"Crossref","is-referenced-by-count":12,"title":["Cutoff for Exact Recovery of Gaussian Mixture Models"],"prefix":"10.1109","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1418-8190","authenticated-orcid":false,"given":"Xiaohui","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yun","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v20-3829"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.3150\/20-BEJ1251"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.09.002"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_4"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"},{"key":"ref37","first-page":"28:1","article-title":"The effectiveness of Lloyd-type methods for the k-means problem","volume":"59","author":"ostrovsky","year":"2013","journal-title":"J ACM"},{"key":"ref36","first-page":"1027","article-title":"K-means++: The advantages of careful seeding","author":"arthur","year":"2007","journal-title":"Proc 18th Annu ACM-SIAM Symp Discrete Algorithms"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1214\/009053607000000640"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2810020"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1214\/009117905000000233"},{"key":"ref61","article-title":"Statistical problems with planted structures: Information-theoretical and computational limits","author":"wu","year":"2018","journal-title":"arXiv 1806 00118"},{"key":"ref63","first-page":"1617","article-title":"Asymptotics of sample eigenstructure for a large dimensional spiked covariance model","volume":"17","author":"paul","year":"2007","journal-title":"Statist Sinica"},{"key":"ref28","first-page":"873","article-title":"Learning segmentation by random walks","author":"meila","year":"2001","journal-title":"Advances in neural information processing systems"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2016.7852287"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688116"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v13-521"},{"key":"ref66","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2545-2","author":"van der vaart","year":"1996","journal-title":"Weak Convergence and Empirical Processes With Applications to Statistics"},{"key":"ref29","first-page":"849","article-title":"On spectral clustering: Analysis and an algorithm","author":"ng","year":"2001","journal-title":"Advances in neural information processing systems"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107337862"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015957395"},{"key":"ref69","first-page":"210","author":"vershynin","year":"2012","journal-title":"Introduction to the Non-Asymptotic Analysis of Random Matrices"},{"key":"ref2","article-title":"The hardness of K-means clustering","author":"dasgupta","year":"2007"},{"key":"ref1","first-page":"281","article-title":"Some methods for classification and analysis of multivariate observations","author":"macqueen","year":"1967","journal-title":"Proc Berkeley Symp on Math Statist and Prob"},{"key":"ref20","article-title":"Statistical guarantees for estimating the centers of a two-component Gaussian mixture by EM","author":"klusowski","year":"2016","journal-title":"arXiv 1608 02280"},{"key":"ref22","first-page":"704","article-title":"Ten steps of em suffice for mixtures of two Gaussians","volume":"65","author":"daskalakis","year":"2017","journal-title":"Proc Conf Learn Theory"},{"key":"ref21","first-page":"6959","article-title":"Convergence of gradient em on multi-component mixture of Gaussians","author":"yan","year":"0","journal-title":"Proc 31st Int Conf Neural Inf Process Syst"},{"key":"ref24","article-title":"Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in $O(\\sqrt{n})$ iterations","author":"wu","year":"2019","journal-title":"arXiv 1908 10935"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1924"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345339"},{"key":"ref25","first-page":"1866","article-title":"Sharp analysis of expectation-maximization for weakly identifiable models","volume":"108","author":"dwivedi","year":"2020","journal-title":"Proc Int Conf Artif Intell Statist"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-015-0659-z"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-016-9341-9"},{"key":"ref59","volume":"139","author":"giraud","year":"2015","journal-title":"Introduction to high-dimensional statistics"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614317"},{"key":"ref55","article-title":"On the tightness of an SDP relaxation of K-means","author":"iguchi","year":"2015","journal-title":"arXiv 1505 04778"},{"key":"ref54","doi-asserted-by":"crossref","first-page":"2211","DOI":"10.1214\/15-AAP1145","article-title":"Belief propagation, robust reconstruction and optimal recovery of block models","volume":"26","author":"mossel","year":"2016","journal-title":"Ann Appl Probab"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1214\/16-EJP4185"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1214\/19-STS715"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax001"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1333-x"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2020.03.002"},{"key":"ref12","first-page":"1931","article-title":"Hidden integrality of SDP relaxations for sub-Gaussian mixture models","volume":"75","author":"fei","year":"2018","journal-title":"Proc 31st Conf on Learn Theory"},{"key":"ref13","first-page":"1795","article-title":"Adaptive clustering through semidefinite programming","author":"royer","year":"2017","journal-title":"Advances in neural information processing systems"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.4171\/MSL\/8"},{"key":"ref15","article-title":"PECOK: A convex optimization approach to variable clustering","author":"bunea","year":"2016","journal-title":"arXiv 1606 05100"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1198\/016214502760047131"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176324464"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1435"},{"key":"ref19","first-page":"2684","article-title":"Global analysis of expectation maximization for mixtures of two Gaussians","author":"xu","year":"2016","journal-title":"Proc 30th Int Conf Neural Inf Process Syst"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"ref3","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/978-3-642-00202-1_24","article-title":"The planar K-means problem is np-hard","author":"mahajan","year":"2009","journal-title":"WALCOM Algorithms Computing"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1561\/0400000025"},{"key":"ref5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","article-title":"Maximum likelihood from incomplete data via the EM algorithm","volume":"39","author":"dempster","year":"1977","journal-title":"J Roy Statist Soc B Statist Methodol"},{"key":"ref8","article-title":"Sharp optimal recovery in the two-component Gaussian mixture model","author":"ndaoud","year":"2018","journal-title":"arXiv 1812 08078"},{"key":"ref7","article-title":"Statistical and computational guarantees of Lloyd’s algorithm and its variants","author":"lu","year":"2016","journal-title":"arXiv 1612 02099"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2594812"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/050641983"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2490670"},{"key":"ref45","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1214\/14-AOS1274","article-title":"Consistency of spectral clustering in stochastic block models","volume":"43","author":"lei","year":"2015","journal-title":"Ann Statist"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2546280"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1545"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591857"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1312486110"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9437270\/09366690.pdf?arnumber=9366690","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T05:47:18Z","timestamp":1724564838000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9366690\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":70,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2021.3063155","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6]]}}}