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

Understand

Orthogonal group synchronization is the problem of estimating $n$ elements $Z_1, \ldots, Z_n$ from the $r \times r$ orthogonal group 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)$.
• Alternatively, Burer--Monteiro-type nonconvex relaxations have generic landscape guarantees at dimension $O(n^{3/2})$.