  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.
