{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T00:39:21Z","timestamp":1791419961687,"version":"4.3.3"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1719558"],"award-info":[{"award-number":["DMS-1719558"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The problem of estimating the phases (angles) of a complex unit-modulus vector $z$ from their noisy pairwise relative measurements $C = zz^* + \\sigma W$, where $W$ is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit--modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for $\\sigma$ up to $\\tilde{\\mathcal{O}}(n^{1\/2})$, yet existing analyses only confirm this observation for $\\sigma$ up to $\\mathcal{O}(n^{1\/4})$. In this paper, we bridge the gap by proving that the SDP relaxation is tight for $\\sigma = \\mathcal{O}(\\sqrt{n \/\\log n})$, and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter $\\ell_\\infty$ bound for the MLE. A novel technique we develop in this paper is to (theoretically) track $n$ closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an $\\ell_\\infty$ perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics.<\/jats:p>","DOI":"10.1137\/17m1122025","type":"journal-article","created":{"date-parts":[[2018,4,3]],"date-time":"2018-04-03T11:33:09Z","timestamp":1522755189000},"page":"989-1016","source":"Crossref","is-referenced-by-count":78,"title":["Near-Optimal Bounds for Phase Synchronization"],"prefix":"10.1137","volume":"28","author":[{"given":"Yiqiao","family":"Zhong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Boumal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,3]]},"reference":[{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1059-6"},{"key":"atypb3","first-page":"1265","author":"Bandeira A. S.","year":"2014","journal-title":"Barcelona"},{"key":"atypb4","first-page":"424","author":"Barbier J.","year":"2016","journal-title":"Barcelona"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1307845110"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.02.007"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2242068"},{"key":"atypb8","unstructured":"N. Boumal,\n                      A Riemannian Low-rank Method for Optimization over Semidefinite Matrices with Block-diagonal Constraints\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1506.00575 arXiv:1506.00575, 2015."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/16M105808X"},{"key":"atypb10","first-page":"1156","author":"Boumal N.","year":"2013","journal-title":"Firenze"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOP394"},{"key":"atypb12","unstructured":"Y. Chen and E. Candes,\n                      The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1609.05820 arXiv:1609.05820, 2016."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/2240092.2240093"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/ias002"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0707001"},{"key":"atypb16","first-page":"2717","author":"Deshpande Y.","year":"2014","journal-title":"NY"},{"key":"atypb17","unstructured":"J. Fan, W. Wang, and Y. Zhong,\n                      An $\\ell^{\\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1603.03516 arXiv:1603.03516, 2016."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"A. Giridhar and P. R. Kumar,\n                      Distributed clock synchronization over wireless networks: Algorithms and analysis\n                      , in Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, CA, 2006, pp. 4915-4920.","DOI":"10.1109\/CDC.2006.377325"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1080\/03610927708827533"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1523097113"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2009.0121"},{"key":"atypb22","first-page":"517","volume":"11","author":"Journe\u0301e M.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb23","unstructured":"M. Lelarge and L. Miolane,\n                      Fundamental Limits of Symmetric Low-rank Matrix Estimation\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1611.03888 arXiv:1611.03888, 2016."},{"key":"atypb24","unstructured":"H. Liu, M.C. Yue, and A. M.C. So,\n                      On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1603.00211 arXiv:1603.00211, 2016."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/110839072"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"D. Martinec and T. Pajdla,\n                      Robust rotation and translation estimation in multiview reconstruction\n                      , in Proceechings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, 2007.","DOI":"10.1109\/CVPR.2007.383115"},{"key":"atypb27","unstructured":"O. Ozyesil, N. Sharon, and A. Singer,\n                      Synchronization over Cartan Motion Groups via Contraction\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1612.00059 arXiv:1612.00059, 2016."},{"key":"atypb28","first-page":"1617","volume":"17","author":"Paul D.","year":"2007","journal-title":"Statist. Sinica"},{"key":"atypb29","unstructured":"A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra,\n                      Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1609.05573 arXiv:1609.05573, 2016."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS887"},{"key":"atypb31","unstructured":"D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard,\n                      A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1611.00128 arXiv:1611.00128, 2016."},{"key":"atypb32","unstructured":"V. Roulet, N. Boumal, and A. d'Aspremont,\n                      Computational Complexity Versus Statistical Performance on Sparse Recovery Problems\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1506.03295 arXiv:1506.03295, 2015."},{"key":"atypb33","unstructured":"M. Rudelson and R. Vershynin,\n                      Non-asymptotic theory of random matrices: Extreme singular values\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1003.2990 arXiv:1003.2990, 2010."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/120863642"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.02.001"},{"key":"atypb36","unstructured":"R. Vershynin,\n                      Introduction to the Non-asymptotic Analysis of Random Matrices\n                      , preprint, \\hrefhttps:\/\/arxiv.org\/abs\/1011.3027 arXiv:1011.3027, 2010."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iat005"},{"key":"atypb39","first-page":"2302","author":"Yu S. X.","year":"2009","journal-title":"Miami, FL"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asv008"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/04061341X"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1122025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:41Z","timestamp":1787338961000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1122025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1122025"],"URL":"https:\/\/doi.org\/10.1137\/17m1122025","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}