{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T15:45:34Z","timestamp":1761061534753,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["CUHK 14208117"],"award-info":[{"award-number":["CUHK 14208117"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11901490"],"award-info":[{"award-number":["11901490"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s10107-021-01715-1","type":"journal-article","created":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T12:03:32Z","timestamp":1636632212000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Non-convex exact community recovery in stochastic block model"],"prefix":"10.1007","volume":"195","author":[{"given":"Peng","family":"Wang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1690-0161","authenticated-orcid":false,"given":"Zirui","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Anthony Man-Cho","family":"So","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,11]]},"reference":[{"key":"1715_CR1","doi-asserted-by":"crossref","unstructured":"Abbe, E.: Community detection and stochastic block models. Foundations and Trends $$^{\\text{\\textregistered} }$$ in Communications and Information Theory 14(1\u20132), 1\u2013162 (2018)","DOI":"10.1561\/0100000067"},{"issue":"1","key":"1715_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","volume":"62","author":"E Abbe","year":"2016","unstructured":"Abbe, E., Bandeira, A.S., Hall, G.: Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory 62(1), 471\u2013487 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"1715_CR3","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1214\/19-AOS1854","volume":"48","author":"E Abbe","year":"2020","unstructured":"Abbe, E., Fan, J., Wang, K., Zhong, Y.: Entrywise eigenvector analysis of random matrices with low expected rank. Annals Stat. 48(3), 1452\u20131474 (2020)","journal-title":"Annals Stat."},{"key":"1715_CR4","doi-asserted-by":"crossref","unstructured":"Abbe, E., Sandon, C.: Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In: Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 670\u2013688 (2015)","DOI":"10.1109\/FOCS.2015.47"},{"issue":"1","key":"1715_CR5","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/j.laa.2005.10.004","volume":"414","author":"PA Absil","year":"2006","unstructured":"Absil, P.A., Edelman, A., Koev, P.: On the largest principal angle between random subspaces. Linear Algebra Appl. 414(1), 288\u2013294 (2006)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1715_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1214\/17-AOS1545","volume":"46","author":"AA Amini","year":"2018","unstructured":"Amini, A.A., Levina, E.: On semidefinite relaxations for the block model. Annals Stat. 46(1), 149\u2013179 (2018)","journal-title":"Annals Stat."},{"issue":"2","key":"1715_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10208-016-9341-9","volume":"18","author":"AS Bandeira","year":"2018","unstructured":"Bandeira, A.S.: Random Laplacian matrices and convex relaxations. Found. Comput. Math. 18(2), 345\u2013379 (2018)","journal-title":"Found. Comput. Math."},{"key":"1715_CR8","unstructured":"Bandeira, A.S., Boumal, N., Voroninski, V.: On the low-rank approach for semidefinite programs arising in synchronization and community detection. In: Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016), pp. 361\u2013382 (2016)"},{"issue":"4","key":"1715_CR9","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1715_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1093\/imanum\/drx080","volume":"39","author":"N Boumal","year":"2018","unstructured":"Boumal, N., Absil, P.A., Cartis, C.: Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numer. Anal. 39(1), 1\u201333 (2018)","journal-title":"IMA J. Numer. Anal."},{"issue":"2","key":"1715_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"20","key":"1715_CR12","doi-asserted-by":"publisher","first-page":"5239","DOI":"10.1109\/TSP.2019.2937282","volume":"67","author":"Y Chi","year":"2019","unstructured":"Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: an overview. IEEE Trans. Signal Process. 67(20), 5239\u20135269 (2019)","journal-title":"IEEE Trans. Signal Process."},{"issue":"10","key":"1715_CR13","doi-asserted-by":"publisher","first-page":"2366","DOI":"10.1038\/nprot.2007.324","volume":"2","author":"MS Cline","year":"2007","unstructured":"Cline, M.S., Smoot, M., Cerami, E., Kuchinsky, A., Landys, N., Workman, C., Christmas, R., Avila-Campilo, I., Creech, M., Gross, B., et al.: Integration of biological networks and gene expression data using cytoscape. Nat. Protocols 2(10), 2366 (2007)","journal-title":"Nat. Protocols"},{"key":"1715_CR14","doi-asserted-by":"crossref","unstructured":"Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw 38(1), (2011)","DOI":"10.1145\/2049662.2049663"},{"issue":"6","key":"1715_CR15","doi-asserted-by":"publisher","first-page":"066106","DOI":"10.1103\/PhysRevE.84.066106","volume":"84","author":"A Decelle","year":"2011","unstructured":"Decelle, A., Krzakala, F., Moore, C., Zdeborov\u00e1, L.: Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84(6), 066106 (2011)","journal-title":"Phys. Rev. E"},{"issue":"3\u20135","key":"1715_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Reports 486(3\u20135), 75\u2013174 (2010)","journal-title":"Phys. Reports"},{"issue":"1","key":"1715_CR17","first-page":"1980","volume":"18","author":"C Gao","year":"2017","unstructured":"Gao, C., Ma, Z., Zhang, A.Y., Zhou, H.H.: Achieving optimal misclassification proportion in stochastic block models. J. Mach. Learn. Res. 18(1), 1980\u20132024 (2017)","journal-title":"J. Mach. Learn. Res."},{"key":"1715_CR18","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"issue":"12","key":"1715_CR19","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99(12), 7821\u20137826 (2002)","journal-title":"Proc. Nat. Acad. Sci."},{"key":"1715_CR20","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix Comput","author":"GH Golub","year":"2013","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Comput, 4th edn. The Johns Hopkins University Press, Baltimore (2013)","edition":"4"},{"issue":"5","key":"1715_CR21","doi-asserted-by":"publisher","first-page":"2788","DOI":"10.1109\/TIT.2016.2546280","volume":"62","author":"B Hajek","year":"2016","unstructured":"Hajek, B., Wu, Y., Xu, J.: Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inf. Theory 62(5), 2788\u20132797 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1715_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1214\/14-AOS1274","volume":"43","author":"J Lei","year":"2015","unstructured":"Lei, J., Rinaldo, A.: Consistency of spectral clustering in stochastic block models. Annals Stat. 43(1), 215\u2013237 (2015)","journal-title":"Annals Stat."},{"issue":"1","key":"1715_CR23","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1137\/18M1224738","volume":"30","author":"X Li","year":"2020","unstructured":"Li, X., Zhu, Z., So, A.M.C., Vidal, R.: Nonconvex robust low-rank matrix recovery. SIAM J. Optim. 30(1), 660\u2013686 (2020)","journal-title":"SIAM J. Optim."},{"key":"1715_CR24","doi-asserted-by":"crossref","unstructured":"Liu, H., Pun, Y.M., So, A.M.C.: Local strong convexity of maximum-likelihood TDOA-based source localization and its algorithmic implications. In: Proceedings of the IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2017), pp. 1\u20135 (2017)","DOI":"10.1109\/CAMSAP.2017.8313119"},{"issue":"4","key":"1715_CR25","doi-asserted-by":"publisher","first-page":"2426","DOI":"10.1137\/16M110109X","volume":"27","author":"H Liu","year":"2017","unstructured":"Liu, H., Yue, M.C., So, A.M.C.: On the estimation performance and convergence rate of the generalized power method for phase synchronization. SIAM J. Optim. 27(4), 2426\u20132446 (2017)","journal-title":"SIAM J. Optim."},{"key":"1715_CR26","doi-asserted-by":"crossref","unstructured":"Liu, H., Yue, M.C., So, A.M.C., Ma, W.K.: A discrete first-order method for large-scale MIMO detection with provable guarantees. In: Proceedings of the 18th IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC 2017), pp. 669\u2013673 (2017)","DOI":"10.1109\/SPAWC.2017.8227768"},{"key":"1715_CR27","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10208-019-09429-9","volume":"20","author":"C Ma","year":"2020","unstructured":"Ma, C., Wang, K., Chi, Y., Chen, Y.: Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Found. Comput. Math. 20, 451\u2013632 (2020)","journal-title":"Found. Comput. Math."},{"key":"1715_CR28","doi-asserted-by":"crossref","unstructured":"Massouli\u00e9, L.: Community detection thresholds and the weak Ramanujan property. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 694\u2013703 (2014)","DOI":"10.1145\/2591796.2591857"},{"issue":"21","key":"1715_CR29","first-page":"1","volume":"21","author":"E Mossel","year":"2016","unstructured":"Mossel, E., Neeman, J., Sly, A.: Consistency thresholds for the planted bisection model. Electron. J. Probability 21(21), 1\u201324 (2016)","journal-title":"Electron. J. Probability"},{"issue":"2","key":"1715_CR30","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"ME Newman","year":"2004","unstructured":"Newman, M.E., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)","journal-title":"Phys. Rev. E"},{"key":"1715_CR31","doi-asserted-by":"crossref","unstructured":"Pun, Y.M., So, A.M.C.: Dynamic regret bound for moving target tracking based on online time-of-arrival measurements. In: Proceedings of the 59th IEEE Conference on Decision and Control (CDC 2020), pp. 5968\u20135973 (2020)","DOI":"10.1109\/CDC42340.2020.9304257"},{"issue":"5","key":"1715_CR32","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1109\/MSP.2020.3004124","volume":"37","author":"R Sun","year":"2020","unstructured":"Sun, R., Li, D., Liang, S., Ding, T., Srikant, R.: The global landscape of neural networks: an overview. IEEE Signal Process. Magazine 37(5), 95\u2013108 (2020)","journal-title":"IEEE Signal Process. Magazine"},{"issue":"2","key":"1715_CR33","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s40305-020-00309-6","volume":"8","author":"RY Sun","year":"2020","unstructured":"Sun, R.Y.: Optimization for deep learning: an overview. J. Oper. Res. Soc. China 8(2), 249\u2013294 (2020)","journal-title":"J. Oper. Res. Soc. China"},{"key":"1715_CR34","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574","volume-title":"Numerical Linear Algebra","author":"LN Trefethen","year":"1997","unstructured":"Trefethen, L.N., Bau, D., III.: Numerical Linear Algebra. SIAM, New Delhi (1997)"},{"issue":"5","key":"1715_CR35","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/MSP.2020.3003541","volume":"37","author":"N Vaswani","year":"2020","unstructured":"Vaswani, N.: Non-convex structured phase retrieval. IEEE Signal Process. Magazine 37(5), 67\u201377 (2020)","journal-title":"IEEE Signal Process. Magazine"},{"key":"1715_CR36","volume-title":"High-Dimensional Probability: an Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability: an Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47. Cambridge University Press, Cambridge (2018)"},{"key":"1715_CR37","unstructured":"Wang, P., Zhou, Z., So, A.M.C.: A nearly-linear time algorithm for exact community recovery in stochastic block model. In: Proceedings of the 37th International Conference on Machine Learning (ICML 2020), pp. 10126\u201310135 (2020)"},{"key":"1715_CR38","unstructured":"Yun, S.Y., Proutiere, A.: Optimal cluster recovery in the labeled stochastic block model. In: D.D. Lee, M.\u00a0Sugiyama, U.V. Luxburg, I.\u00a0Guyon, R.\u00a0Garnett (eds.) Advances in Neural Information Processing Systems 29: Proceedings of the 2016 Conference, pp. 965\u2013973 (2016)"},{"issue":"2","key":"1715_CR39","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1137\/17M1122025","volume":"28","author":"Y Zhong","year":"2018","unstructured":"Zhong, Y., Boumal, N.: Near-optimal bounds for phase synchronization. SIAM J. Optim. 28(2), 989\u20131016 (2018)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01715-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01715-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01715-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T23:28:56Z","timestamp":1673738936000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01715-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,11]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1715"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01715-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,11,11]]},"assertion":[{"value":"13 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}