# Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 44 references that are in the map.
- First posted on arXiv 15 Mar 2021.

## Builds on (most cited first, 11 of 11)

- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [NeuRoRA: Neural Robust Rotation Averaging](https://mlsanity.com/paper/1912.04485/) (2019)
- [Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models](https://mlsanity.com/paper/1810.11692/) (2018)
- [One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers](https://mlsanity.com/paper/2006.06769/) (2020)
- [Distributed Certifiably Correct Pose-Graph Optimization](https://mlsanity.com/paper/1911.03721/) (2019)
- [Visual SLAM: Why Bundle Adjust?](https://mlsanity.com/paper/1902.03747/) (2019)
- [Progressive Structure from Motion](https://mlsanity.com/paper/1803.07349/) (2018)
- [GSLAM: Initialization-robust Monocular Visual SLAM via Global Structure-from-Motion](https://mlsanity.com/paper/1708.04814/) (2017)
- [Hybrid Camera Pose Estimation with Online Partitioning for SLAM](https://mlsanity.com/paper/1908.01797/) (2019)

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

- [HARA: A Hierarchical Approach for Robust Rotation Averaging](https://mlsanity.com/paper/2111.08831/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [GlobalPointer: Large-Scale Plane Adjustment with Bi-Convex Relaxation](https://mlsanity.com/paper/2407.13537/) (2024)
- [RAGO: Recurrent Graph Optimizer For Multiple Rotation Averaging](https://mlsanity.com/paper/2212.07211/) (2022)
- [Distributed Global Structure-from-Motion with a Deep Front-End](https://mlsanity.com/paper/2311.18801/) (2023)
- [Rotation Synchronization via Deep Matrix Factorization](https://mlsanity.com/paper/2305.05268/) (2023)
- [Invertible Neural Warp for NeRF](https://mlsanity.com/paper/2407.12354/) (2024)
- [Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization](https://mlsanity.com/paper/2407.04260/) (2024)
- [Towards Initialization-free Calibrated Bundle Adjustment](https://mlsanity.com/paper/2506.23808/) (2025)
- [Certifiably Optimal Anisotropic Rotation Averaging](https://mlsanity.com/paper/2503.07353/) (2025)
- [A Taxonomy of Structure from Motion Methods](https://mlsanity.com/paper/2505.15814/) (2025)
- [Incremental Rotation Averaging Revisited](https://mlsanity.com/paper/2309.16924/) (2023)
- [VICAN: Very Efficient Calibration Algorithm for Large Camera Networks](https://mlsanity.com/paper/2405.10952/) (2024)
- [Making Rotation Averaging Fast and Robust with Anisotropic Coordinate Descent](https://mlsanity.com/paper/2506.01940/) (2025)

## Abstract (arXiv)

Under mild conditions on the noise level of the measurements, rotation averaging satisfies strong duality, which enables global solutions to be obtained via semidefinite programming (SDP) relaxation. However, generic solvers for SDP are rather slow in practice, even on rotation averaging instances of moderate size, thus developing specialised algorithms is vital. In this paper, we present a fast algorithm that achieves global optimality called rotation coordinate descent (RCD). Unlike block coordinate descent (BCD) which solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD directly maintains and updates all valid rotations throughout the iterations. This obviates the need to store a large dense semidefinite matrix. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods on a variety of problem configurations. Maintaining valid rotations also facilitates incorporating local optimisation routines for further speed-ups. Moreover, our algorithm is simple to implement; see supplementary material for a demonstration program.