IDeAS Seminar: Near-optimal bounds for phase synchronization

Wed, May 10, 2017, 2:30 pm

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.

Fine Hall 224
Event category: 

Upcoming Events

Prof. Afonso Bandeira, ETH Zurich

Mon, Sep 11, 2023, 4:30 pm
Location: 214 Fine Hall

Prof. Jonathan Pillow, Princeton University

Mon, Sep 18, 2023, 4:30 pm
Location: 214 Fine Hall

No PACM Colloquium scheduled on this day-Yom Kippur

Mon, Sep 25, 2023, 4:30 pm
Location: 214 Fine Hall