Multi-Frequency Phase Synchronization
Preprint
Abstract
We propose a novel formulation for phase synchronization -- the statistical problem of jointly estimating alignment angles from noisy pairwise comparisons -- as a nonconvex optimization problem that enforces consistency among the pairwise comparisons in multiple frequency channels. Inspired by harmonic retrieval in signal processing, we develop a simple yet efficient two-stage algorithm that leverages the multi-frequency information. We demonstrate in theory and practice that the proposed algorithm significantly outperforms state-of-the-art phase synchronization algorithms, at a mild computational costs incurred by using the extra frequency channels. We also extend our algorithmic framework to general synchronization problems over compact Lie groups.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Non-unique games over compact groups and orientation estimation in cryo-EMInverse Problems, 2020
- The Geometry of Synchronization Problems and Learning Group ActionsDiscrete & Computational Geometry, 2019
- Message‐Passing Algorithms for Synchronization Problems over Compact GroupsCommunications on Pure and Applied Mathematics, 2018
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronizationMathematical Programming, 2016
- Approximating the little Grothendieck problem over the orthogonal and unitary groupsMathematical Programming, 2016
- Eigenvector synchronization, graph rigidity and the molecule problemInformation and Inference: A Journal of the IMA, 2012
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- ESPRIT-estimation of signal parameters via rotational invariance techniquesIEEE Transactions on Acoustics, Speech, and Signal Processing, 1989
- Maximum likelihood localization of multiple sources by alternating projectionIEEE Transactions on Acoustics, Speech, and Signal Processing, 1988
- Estimation of frequencies of multiple sinusoids: Making linear prediction perform like maximum likelihoodProceedings of the IEEE, 1982