On the estimation performance and convergence rate of the generalized power method for phase synchronization

Abstract

An estimation problem of fundamental interest is that of phase (or angular) synchronization, in which the goal is to recover a collection of phases (or angles) using noisy measurements of relative phases (or angle offsets). It is known that in the Gaussian noise setting, the maximum likelihood estimator (MLE) is an optimal solution to a nonconvex quadratic optimization problem and can be found with high probability using semidefinite programming (SDP), provided that the noise power is not too large. In this paper, we study the estimation and convergence performance of a recently proposed low-complexity alternative to the SDP-based approach, namely, the generalized power method (GPM). Our contribution is twofold. First, we show that the sequence of estimation errors associated with the GPM iterates is bounded above by a decreasing sequence. As a corollary, we show that all iterates achieve an estimation error that is on the same order as that of an MLE. Our result holds under the least restrictive assumption on the noise power and gives the best provable bound on the estimation error known to date. It also implies that one can terminate the GPM at any iteration and still obtain an estimator that has a theoretical guarantee on its estimation error. Second, we show that under the same assumption on the noise power as that in [A. S. Bandeira, N. Boumal, and A. Singer, Math. Program. Ser. A, 163 (2017), pp. 145–167] for the SDP-based method, the GPM will converge to an MLE at a linear rate with high probability. This answers a question raised in [N. Boumal, SIAM J. Optim., 26 (2016), pp. 2355–2377] and shows that the GPM is competitive in terms of both theoretical guarantees and numerical efficiency with the SDP-based method. At the heart of our convergence rate analysis is a new error bound for the nonconvex quadratic optimization formulation of the phase synchronization problem, which could be of independent interest. As a by-product, we give an alternative proof of a result in [N. Boumal, SIAM J. Optim., 26 (2016), pp. 2355–2377], which asserts that every second-order critical point of the aforementioned nonconvex quadratic optimization formulation is globally optimal in a certain noise regime.