IDeAS Seminar: Near-optimal bounds for phase synchronization

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.

Yiqiao Zhong is a 3rd year PhD student from the department of operations research and financial engineering at Princeton University, advised by Prof. Jianqing Fan. He received his B.S. from Peking University in 2014. His main research interests include high-dimensional statistics, nonconvex optimization and machine learning.