Near-optimal bounds for phase synchronization

The problem of phase synchronization is to estimate the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz^* + σ W, where W is a complex-valued Gaussian random matrix. 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 relaxation (SDP) approach or the generalized power method (GPM) to solve it. Numerical experiments suggest both of these methods succeed with high probability for σ up to tildeO(n1/2), yet, existing analyses only confirm this observation for σ up to O(n1/4). In this paper, we bridge the gap, by proving SDP is tight for σ = O(√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 ℓ_∞ bound for the MLE. A novel technique we develop in this paper is to track (theoretically) n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an ℓ_∞ perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.