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

Orthogonal group synchronization is the problem of estimating n elements Z1, ldots, Zn from the r × r orthogonal group given some relative measurements Rij ≈ ZiZj-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(n2). 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 Y1, ldots, Yn. For p ≥ r, each Yi 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.