Near-optimal bounds for phase synchronization
Authors:
- Nicolas BoumalNBNicolas Boumal
Preprint
Abstract
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^* + \sigma 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 $\sigma$ up to $\tilde{\mathcal{O}}(n^{1/2})$, yet, existing analyses only confirm this observation for $\sigma$ up to $\mathcal{O}(n^{1/4})$. In this paper, we bridge the gap, by proving SDP is tight for $\sigma = \mathcal{O}(\sqrt{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 $\ell_\infty$ 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 $\ell_\infty$ perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise DifferencesCommunications on Pure and Applied Mathematics, 2018
- Fundamental limits of symmetric low-rank matrix estimationProbability Theory and Related Fields, 2018
- Random Laplacian Matrices and Convex RelaxationsFoundations of Computational Mathematics, 2016
- Phase transitions in semidefinite relaxationsProceedings of the National Academy of Sciences, 2016
- Exact and stable recovery of rotations for robust synchronizationInformation and Inference: A Journal of the IMA, 2013
- Optimal M-estimation in high-dimensional regressionProceedings of the National Academy of Sciences, 2013
- Introduction to the non-asymptotic analysis of random matrices2012
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- Complex Quadratic Optimization and Semidefinite ProgrammingSIAM Journal on Optimization, 2006
- The Rotation of Eigenvectors by a Perturbation. IIISIAM Journal on Numerical Analysis, 1970