Near-Optimal Bounds for Phase Synchronization

Abstract

The problem of phase synchronization is to estimate the phases (angles) of a\ncomplex unit-modulus vector $z$ from their noisy pairwise relative measurements\n$C = zz^* + \\sigma W$, where $W$ is a complex-valued Gaussian random matrix.\nThe maximum likelihood estimator (MLE) is a solution to a unit-modulus\nconstrained quadratic programming problem, which is nonconvex. Existing works\nhave proposed polynomial-time algorithms such as a semidefinite relaxation\n(SDP) approach or the generalized power method (GPM) to solve it. Numerical\nexperiments suggest both of these methods succeed with high probability for\n$\\sigma$ up to $\\tilde{\\mathcal{O}}(n^{1/2})$, yet, existing analyses only\nconfirm this observation for $\\sigma$ up to $\\mathcal{O}(n^{1/4})$. In this\npaper, we bridge the gap, by proving SDP is tight for $\\sigma =\n\\mathcal{O}(\\sqrt{n /\\log n})$, and GPM converges to the global optimum under\nthe same regime. Moreover, we establish a linear convergence rate for GPM, and\nderive a tighter $\\ell_\\infty$ bound for the MLE. A novel technique we develop\nin this paper is to track (theoretically) $n$ closely related sequences of\niterates, in addition to the sequence of iterates GPM actually produces. As a\nby-product, we obtain an $\\ell_\\infty$ perturbation bound for leading\neigenvectors. Our result also confirms intuitions that use techniques from\nstatistical mechanics.\n