TY - JOUR
T1 - Near-optimal bounds for phase synchronization∗
AU - Zhong, Yiqiao
AU - Boumal, Nicolas
N1 - Funding Information:
∗Received by the editors March 21, 2017; accepted for publication (in revised form) December 8, 2017; published electronically April 3, 2018. http://www.siam.org/journals/siopt/28-2/M112202.html Funding: The second author is supported by NSF grant DMS-1719558. †Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ 08544 (yiqiaoz@princeton.edu). ‡Department of Mathematics and the Program in Applied and Computational Mathematics, Princeton University, Princeton, NJ 08544 (nboumal@math.princeton.edu). 1Since W is Gaussian, an MLE minimizes the squared Frobenius norm: ‖C − xx∗‖F2 = ‖C‖F2 + ‖xx∗‖F2 − 2x∗Cx. Owing to |xk| = 1 ∀k, this is equivalent to maximizing x∗Cx.
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.
PY - 2018
Y1 - 2018
N2 - The problem of estimating the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz∗ + σW, where W is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit–modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for σ up to Õ(n1/2), yet existing analyses only confirm this observation for σ up to O(n1/4). In this paper, we bridge the gap by proving that the SDP relaxation is tight for σ = O(n/log n), and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter ∞ bound for the MLE. A novel technique we develop in this paper is to (theoretically) track n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an ∞ perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics.
AB - The problem of estimating the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz∗ + σW, where W is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit–modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for σ up to Õ(n1/2), yet existing analyses only confirm this observation for σ up to O(n1/4). In this paper, we bridge the gap by proving that the SDP relaxation is tight for σ = O(n/log n), and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter ∞ bound for the MLE. A novel technique we develop in this paper is to (theoretically) track n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an ∞ perturbation bound for leading eigenvectors. Our result also confirms predictions that use techniques from statistical mechanics.
KW - Angular synchronization
KW - Eigenvector perturbation bound
KW - Maximum likelihood estimator
KW - Nonconvex optimization
KW - Projected power method
KW - Quadratically constrained quadratic program
KW - Semidefinite programming relaxation
UR - http://www.scopus.com/inward/record.url?scp=85049664864&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049664864&partnerID=8YFLogxK
U2 - 10.1137/17M1122025
DO - 10.1137/17M1122025
M3 - Article
AN - SCOPUS:85049664864
SN - 1052-6234
VL - 28
SP - 989
EP - 1016
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 2
ER -