Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs

Abstract

Orthogonal group synchronization is the problem of estimating $n$ elements $Z_1,\dots ,Z_n$ from the $r\times r$ orthogonal group given some relative measurements $R_{ij}\approx Z_i^{}{Z}_j^{-1}$. The least-squares formulation is nonconvex. To avoid its local minima, a Shor-type convex relaxation squares the dimension of the optimization problem from $O(n)$ to $O(n^2)$. Alternatively, Burer--Monteiro-type nonconvex relaxations have generic landscape guarantees at dimension $O(n^{3/2})$. For smaller relaxations, the problem structure matters. It has been observed in the robotics literature that, for SLAM problems, it seems sufficient to increase the dimension by a small constant multiple over the original. We partially explain this. This also has implications for Kuramoto oscillators. Specifically, we minimize the least-squares cost function in terms of estimators $Y_1,\dots ,Y_n$. For $p\ge r$, each $Y_i$ is relaxed to the Stiefel manifold $\mathrm{St}(r,p)$ of $r\times p$ matrices with orthonormal rows. The available measurements implicitly define a (connected) graph $G$ on $n$ vertices. In the noiseless case, we show that, for all connected graphs $G$, second-order critical points are globally optimal as soon as $p\ge r+2$. (This implies that Kuramoto oscillators on $\mathrm{St}(r,p)$ synchronize for all $p\ge r+2$.) This result is the best possible for general graphs; the previous best known result requires $2p\ge 3(r+1)$. For $p>r+2$, our result is robust to modest amounts of noise (depending on $p$ and $G$). Our proof uses a novel randomized choice of tangent direction to prove (near-)optimality of second-order critical points. Finally, we partially extend our noiseless landscape results to the complex case (unitary group); we show that there are no spurious local minima when $2p\ge 3r$.

References in corpus (9)

• Low-rank optimization for semidefinite convex problems
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Synchronization and Stability for Quantum Kuramoto
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• There are no non-zero Stable Fixed Points for dense networks in the homogeneous Kuramoto model
• Relations for certain symmetric norms and anti-norms before and after partial trace
• Sufficiently dense Kuramoto networks are globally synchronizing
• Synchronization of Kuramoto Oscillators in Dense Networks
• The lower bound of the network connectivity guaranteeing in-phase synchronization

Cited by in corpus (1)

• Nonconvex landscapes for ${\mathbf{Z}}_2$ synchronization and graph clustering are benign near exact recovery thresholds