  Orthogonal group synchronization is the problem of estimating $n$ elements
$Z_1, \ldots, Z_n$ from the orthogonal group $\mathrm{O}(r)$ given some
relative measurements $R_{ij} \approx 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)$. 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
nonconvex relaxations of only slightly increased dimension seem sufficient for
SLAM problems. 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, \ldots, Y_n$. Each $Y_i$ is relaxed to the Stiefel manifold
$\mathrm{St}(r, p)$ of $r \times p$ matrices with orthonormal rows. The
available measurements implicitly define a (connected) graph $G$ on $n$
vertices. In the noiseless case, we show that second-order critical points are
globally optimal as soon as $p \geq r+2$ for all connected graphs $G$. (This
implies that Kuramoto oscillators on $\mathrm{St}(r, p)$ synchronize for all $p
\geq r + 2$.) This result is the best possible for general graphs; the previous
best known result requires $2p \geq 3(r + 1)$. For $p > r + 2$, our result is
robust to modest amounts of noise (depending on $p$ and $G$). When local minima
remain, they still achieve minimax-optimal error rates. 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), showing that there are no spurious local minima when $2p
\geq 3r$.
