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ⱼ⁻¹. 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(n3/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₁, …, 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.