Near-optimal bounds for phase synchronization

Yiqiao Zhong, Nicolas Boumal

Research output: Contribution to journalArticle

16 Scopus citations

Abstract

The problem of estimating 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, 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 σ up to Õ(n1/2), yet existing analyses only confirm this observation for σ up to O(n1/4). In this paper, we bridge the gap by proving that the SDP relaxation 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 (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 ∞ perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics.

Original languageEnglish (US)
Pages (from-to)989-1016
Number of pages28
JournalSIAM Journal on Optimization
Volume28
Issue number2
DOIs
StatePublished - Jan 1 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Angular synchronization
  • Eigenvector perturbation bound
  • Maximum likelihood estimator
  • Nonconvex optimization
  • Projected power method
  • Quadratically constrained quadratic program
  • Semidefinite programming relaxation

Fingerprint Dive into the research topics of 'Near-optimal bounds for phase synchronization<sup>∗</sup>'. Together they form a unique fingerprint.

  • Cite this