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

arXiv: https://arxiv.org/abs/2307.02941 · HTML: https://mlsanity.com/paper/2307.02941/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2023.

## Built on by (most cited first, 6 of 6)

- [Synchronization on circles and spheres with nonlinear interactions](https://mlsanity.com/paper/2405.18273/) (2024)
- [Probe-Free Low-Rank Activation Intervention](https://mlsanity.com/paper/2502.04043/) (2025)
- [A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints](https://mlsanity.com/paper/2501.13830/) (2025)
- [A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization](https://mlsanity.com/paper/2506.20344/) (2025)
- [Sparse Variable Projection in Robotic Perception: Exploiting Separable Structure for Efficient Nonlinear Optimization](https://mlsanity.com/paper/2512.07969/) (2025)
- [Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs](https://mlsanity.com/paper/2411.03103/) (2024)

## Abstract (arXiv)

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.