Nonconvex phase synchronization

Nicolas Boumal

Research output: Contribution to journalArticlepeer-review

106 Scopus citations

Abstract

We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.

Original languageEnglish (US)
Pages (from-to)2355-2377
Number of pages23
JournalSIAM Journal on Optimization
Volume26
Issue number4
DOIs
StatePublished - 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Angular synchronization
  • Generalized power method
  • Nonconvex optimization
  • Optimization on manifolds
  • Projected power method
  • Quadratically constrained quadratic pro- gramming
  • Sufficient optimality conditions

Fingerprint

Dive into the research topics of 'Nonconvex phase synchronization'. Together they form a unique fingerprint.

Cite this