# Distributed Certifiably Correct Pose-Graph Optimization

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2019.

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

- [Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems](https://mlsanity.com/paper/2106.14386/) (2021)
- [RAYEN: Imposition of Hard Convex Constraints on Neural Networks](https://mlsanity.com/paper/2307.08336/) (2023)
- [Swarm-SLAM : Sparse Decentralized Collaborative Simultaneous Localization and Mapping Framework for Multi-Robot Systems](https://mlsanity.com/paper/2301.06230/) (2023)
- [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)
- [Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging](https://mlsanity.com/paper/2103.08292/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [A Robot Web for Distributed Many-Device Localisation](https://mlsanity.com/paper/2202.03314/) (2022)
- [Building Rome with Convex Optimization](https://mlsanity.com/paper/2502.04640/) (2025)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [RL-PGO: Reinforcement Learning-based Planar Pose-Graph Optimization](https://mlsanity.com/paper/2202.13221/) (2022)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)
- [Detection and Recovery of Adversarial Slow-Pose Drift in Offloaded Visual-Inertial Odometry](https://mlsanity.com/paper/2509.07130/) (2025)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Policies over Poses: Reinforcement Learning based Distributed Pose-Graph Optimization for Multi-Robot SLAM](https://mlsanity.com/paper/2510.22740/) (2025)
- [DVM-SLAM: Decentralized Visual Monocular Simultaneous Localization and Mapping for Multi-Agent Systems](https://mlsanity.com/paper/2503.04126/) (2025)
- [Certifiable Factor Graph Optimization](https://mlsanity.com/paper/2603.01267/) (2026)

## Abstract (arXiv)

This paper presents the first certifiably correct algorithm for distributed pose-graph optimization (PGO), the backbone of modern collaborative simultaneous localization and mapping (CSLAM) and camera network localization (CNL) systems. Our method is based upon a sparse semidefinite relaxation that we prove provides globally-optimal PGO solutions under moderate measurement noise (matching the guarantees enjoyed by state-of-the-art centralized methods), but is amenable to distributed optimization using the low-rank Riemannian Staircase framework. To implement the Riemannian Staircase in the distributed setting, we develop Riemannian block coordinate descent (RBCD), a novel method for (locally) minimizing a function over a product of Riemannian manifolds. We also propose the first distributed solution verification and saddle escape methods to certify the global optimality of critical points recovered via RBCD, and to descend from suboptimal critical points (if necessary). All components of our approach are inherently decentralized: they require only local communication, provide privacy protection, and are easily parallelizable. Extensive evaluations on synthetic and real-world datasets demonstrate that the proposed method correctly recovers globally optimal solutions under moderate noise, and outperforms alternative distributed techniques in terms of solution precision and convergence speed.