Benign Landscapes of Low-Dimensional Relaxations for Orthogonal Synchronization on General Graphs

.Orthogonal group synchronization is the problem of estimating \(n\) elements \(Z_1, …, Z_n\) from the \(r × r\) orthogonal group given some relative measurements \(Rᵢⱼ ≈ Z_i^{}Z_j⁻¹\). 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(n3/2)\). For smaller relaxations, the problem structure matters. It has been observed in the robotics literature that, for simultaneous localization and mapping 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, …, Y_n\). For \(p ≥ r\), each \(Y_i\) is relaxed to the Stiefel manifold \(St(r, p)\) of \(r × 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 ≥ r+2\). (This implies that Kuramoto oscillators on \(St(r, p)\) synchronize for all \(p ≥ r+2\).) This result is the best possible for general graphs; the previous best known result requires \(2p ≥ 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 ≥ 3r\).