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

. Orthogonal group synchronization is the problem of estimating \ (n\) elements \ (Z₁, , Zₙ\) from the \ (r r\) orthogonal group given some relative measurements \ (R₈₉ Zᵢ^Zⱼ^-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²) \). 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 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₁, , Yₙ\). For \ (p r\), each \ (Yᵢ\) 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\). Keywordsoptimization landscapenonconvex optimizationorthogonal group synchronizationquadratically constrained quadratic programBurer–Monteiro factorizationKuramoto modelMSC codes90C2690C3090C3590C46