Skip to main content


Author(s): Zhong, Yiqiao; Boumal, Nicolas

To refer to this page use:
Abstract: 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 unitmodulus-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 <(O)overtilde>(n(1/2)), yet existing analyses only confirm this observation for sigma up to <(O)overtilde>(n(1/2)). In this paper, we bridge the gap by proving that the SDP relaxation is tight for sigma = O(root 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 l(infinity) 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 l(infinity) perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics.
Publication Date: 2018
Electronic Publication Date: 3-Apr-2018
Citation: Zhong, Yiqiao, Boumal, Nicolas. (2018). NEAR-OPTIMAL BOUNDS FOR PHASE SYNCHRONIZATION. SIAM JOURNAL ON OPTIMIZATION, 28 (989 - 1016. doi:10.1137/17M1122025
DOI: doi:10.1137/17M1122025
ISSN: 1052-6234
EISSN: 1095-7189
Pages: 989 - 1016
Type of Material: Journal Article
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.