Near-optimal bounds for phase synchronization

-
Joe Zhong, Princeton University
Fine Hall 224

The problem of phase synchronization is to estimate the phases (angles) of a complex unit-modulus vector from their noisy pairwise relative measurements. It is motivated by applications such as cryo-EM, camera orientation estimation, time synchronization of distributed networks, etc. This problem is usually formulated as a nonconvex optimization problem, and many methods, including semidefinite programming (SDP) and generalized power method (GPM), have been proposed to solve it.  Though a simpler problem (Z_2 synchronization) is well understood, a lack of understanding of the properties of the optimization problem, especially statistical dependence, has led to suboptimal results in analysis. In particular, there is a gap, in terms of signal-to-noise ratio (SNR), between analysis and numerical experiments. In this talk, we bridge this gap, by proving that SDP is tight, under a near-optimal SNR (up to a log factor); and that GPM converges to the global optimum under the same regime. We also derive a tighter entrywise 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 entrywise perturbation bound for leading eigenvectors, which is of independent interest.