TY - JOUR
T1 - Nonconvex phase synchronization
AU - Boumal, Nicolas
N1 - Funding Information:
This research was generously supported by the Fonds Speciaux de Recherche (FSR) from UCLouvain and, thanks to A. d'Aspremont, by the Chaire Havas Chaire Economie et gestion des nouvelles donnees, ERC Starting Grant SIPA, and a Research in Paris grant.
Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.
PY - 2016
Y1 - 2016
N2 - We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.
AB - We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.
KW - Angular synchronization
KW - Generalized power method
KW - Nonconvex optimization
KW - Optimization on manifolds
KW - Projected power method
KW - Quadratically constrained quadratic pro- gramming
KW - Sufficient optimality conditions
UR - http://www.scopus.com/inward/record.url?scp=85007223418&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85007223418&partnerID=8YFLogxK
U2 - 10.1137/16M105808X
DO - 10.1137/16M105808X
M3 - Article
AN - SCOPUS:85007223418
SN - 1052-6234
VL - 26
SP - 2355
EP - 2377
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 4
ER -