# Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2019.

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

- [Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach](https://mlsanity.com/paper/2101.09116/) (2021)
- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)

## Abstract (arXiv)

The so-called Burer-Monteiro method is a well-studied technique for solving large-scale semidefinite programs (SDPs) via low-rank factorization. The main idea is to solve rank-restricted, albeit non-convex, surrogates instead of the SDP. Recent works have shown that, in an important class of SDPs with elegant geometric structure, one can find globally optimal solutions to the SDP by finding rank-deficient second-order critical points of an unconstrained Riemannian optimization problem. Hence, in such problems, the Burer-Monteiro approach can provide a scalable and reliable alternative to interior-point methods that scale poorly. Among various Riemannian optimization methods proposed, block-coordinate minimization (BCM) is of particular interest due to its simplicity. Erdogdu et al. in their recent work proposed BCM for problems over the Cartesian product of unit spheres and provided global convergence rate estimates for the algorithm. This report extends the BCM algorithm and the global convergence rate analysis of Erdogdu et al. from problems over the Cartesian product of unit spheres to the Cartesian product of Stiefel manifolds. The latter more general setting has important applications such as synchronization over the special orthogonal (SO) and special Euclidean (SE) groups.