# A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2015.

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

- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach](https://mlsanity.com/paper/2101.09116/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs](https://mlsanity.com/paper/2109.08046/) (2021)
- [On the Tightness of Semidefinite Relaxations for Rotation Estimation](https://mlsanity.com/paper/2101.02099/) (2021)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method](https://mlsanity.com/paper/2112.06556/) (2021)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)
- [A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints](https://mlsanity.com/paper/2501.13830/) (2025)
- [NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization](https://mlsanity.com/paper/2604.07372/) (2026)
- [From Digital Humanities to Quantum Humanities: Potentials and Applications](https://mlsanity.com/paper/2103.11825/) (2021)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Rotation Averaging: A Primal-Dual Method and Closed-Forms in Cycle Graphs](https://mlsanity.com/paper/2406.18564/) (2024)
- [Making Rotation Averaging Fast and Robust with Anisotropic Coordinate Descent](https://mlsanity.com/paper/2506.01940/) (2025)
- [Certifiable Factor Graph Optimization](https://mlsanity.com/paper/2603.01267/) (2026)
- [(DNN)2: Doubly Non-Negative Relaxations for Deep Neural Networks](https://mlsanity.com/paper/2608.24743/) (2026)

## Abstract (arXiv)

We propose a new algorithm to solve optimization problems of the form min f(X) for a smooth function f under the constraints that X is positive semidefinite and the diagonal blocks of X are small identity matrices. Such problems often arise as the result of relaxing a rank constraint (lifting). In particular, many estimation tasks involving phases, rotations, orthonormal bases or permutations fit in this framework, and so do certain relaxations of combinatorial problems such as Max-Cut. The proposed algorithm exploits the facts that (1) such formulations admit low-rank solutions, and (2) their rank-restricted versions are smooth optimization problems on a Riemannian manifold. Combining insights from both the Riemannian and the convex geometries of the problem, we characterize when second-order critical points of the smooth problem reveal KKT points of the semidefinite problem. We compare against state of the art, mature software and find that, on certain interesting problem instances, what we call the staircase method is orders of magnitude faster, is more accurate and scales better. Code is available.