# Certifiable Factor Graph Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 53 references that are in the map.
- First posted on arXiv 1 Mar 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Age](https://mlsanity.com/paper/1606.05830/) (2016)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization](https://mlsanity.com/paper/1706.02586/) (2017)
- [Distributed Certifiably Correct Pose-Graph Optimization](https://mlsanity.com/paper/1911.03721/) (2019)
- [A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints](https://mlsanity.com/paper/1506.00575/) (2015)
- [A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics](https://mlsanity.com/paper/1908.05209/) (2019)
- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [On the local stability of semidefinite relaxations](https://mlsanity.com/paper/1710.04287/) (2017)
- [An Efficient Global Optimality Certificate for Landmark-Based SLAM](https://mlsanity.com/paper/2206.12961/) (2022)
- [Building Rome with Convex Optimization](https://mlsanity.com/paper/2502.04640/) (2025)
- [Certifiably Correct Range-Aided SLAM](https://mlsanity.com/paper/2302.11614/) (2023)
- [SCORE: A Second-Order Conic Initialization for Range-Aided SLAM](https://mlsanity.com/paper/2210.03177/) (2022)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation](https://mlsanity.com/paper/2007.06708/) (2020)
- [Accelerating Certifiable Estimation with Preconditioned Eigensolvers](https://mlsanity.com/paper/2207.05257/) (2022)

## Abstract (arXiv)

We show that the factor graph and certifiable estimation paradigms, which have thus far been treated as essentially independent in the literature, can be naturally synthesized into a unified framework for certifiable factor graph optimization that combines the ease of use of the former with the strong performance guarantees of the latter. The key insight enabling our synthesis is that the core mathematical constructions used to develop certifiable estimators (Shor's relaxation and Burer-Monteiro factorization) inherit a factor graph structure from the original problem: applying these transformations to a QCQP-representable estimation task with an associated factor graph model yields a lifted problem with identical factor graph connectivity whose constituent variables and factors are simple one-to-one algebraic transformations (lifts) of those appearing in the original QCQP's factor graph. This correspondence enables the Riemannian Staircase methodology for certifiable estimation to be easily instantiated and deployed using the same mature, highly-performant factor graph libraries and workflows already ubiquitously employed throughout robotics and computer vision. Experimental evaluation on a variety of pose graph optimization, landmark SLAM, and range-aided SLAM benchmarks demonstrates that our certifiable factor graph optimization methodology enables the implementation of certifiable estimators that are functionally equivalent to current state-of-the-art hand-designed, problem-specific methods, while dramatically reducing the required implementation effort from the order of months to hours.