# An Efficient Global Optimality Certificate for Landmark-Based SLAM

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2022.

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

- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023)
- [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)
- [Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis](https://mlsanity.com/paper/2508.15613/) (2025)
- [Learning to Anchor Visual Odometry: KAN-Based Pose Regression for Planetary Landing](https://mlsanity.com/paper/2602.06968/) (2025)
- [Incremental Mapping with Measurement Synchronization & Compression](https://mlsanity.com/paper/2602.07901/) (2026)
- [Certifiable Factor Graph Optimization](https://mlsanity.com/paper/2603.01267/) (2026)
- [Dr-BA: Separable Optimization for Direct Radar Bundle Adjustment & Localization](https://mlsanity.com/paper/2605.07041/) (2026)

## Abstract (arXiv)

Modern state estimation is often formulated as an optimization problem and solved using efficient local search methods. These methods at best guarantee convergence to local minima, but, in some cases, global optimality can also be certified. Although such global optimality certificates have been well established for 3D textitpose-graph optimization, the details have yet to be worked out for the 3D landmark-based SLAM problem, in which estimated states include both robot poses and map landmarks. In this paper, we address this gap by using a graph-theoretic approach to cast the subproblems of landmark-based SLAM into a form that yields a sufficient condition for global optimality. Efficient methods of computing the optimality certificates for these subproblems exist, but first require the construction of a large data matrix. We show that this matrix can be constructed with complexity that remains linear in the number of landmarks and does not exceed the state-of-the-art computational complexity of one local solver iteration. We demonstrate the efficacy of the certificate on simulated and real-world landmark-based SLAM problems. We also integrate our method into the state-of-the-art SE-Sync pipeline to efficiently solve landmark-based SLAM problems to global optimality. Finally, we study the robustness of the global optimality certificate to measurement noise, taking into consideration the effect of the underlying measurement graph.