BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to 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 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,& mldr;,Y-n. For p >= r, each Y-i is relaxed to the Stiefel manifold St(r,p) of r x 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.