# Convex Relaxations for Pose Graph Optimization with Outliers

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2018.

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

- [Global Structure-from-Motion Revisited](https://mlsanity.com/paper/2407.20219/) (2024)
- [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)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms](https://mlsanity.com/paper/2302.07184/) (2023)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator](https://mlsanity.com/paper/2409.13978/) (2024)
- [Gravity-aligned Rotation Averaging with Circular Regression](https://mlsanity.com/paper/2410.12763/) (2024)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Robust Self-Tuning Data Association for Geo-Referencing Using Lane Markings](https://mlsanity.com/paper/2207.14042/) (2022)
- [SLAM assisted 3D tracking system for laparoscopic surgery](https://mlsanity.com/paper/2409.11688/) (2024)
- [Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis](https://mlsanity.com/paper/2508.15613/) (2025)
- [Making Rotation Averaging Fast and Robust with Anisotropic Coordinate Descent](https://mlsanity.com/paper/2506.01940/) (2025)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [RiemanLine: Riemannian Manifold Representation of 3D Lines for Factor Graph Optimization](https://mlsanity.com/paper/2508.04335/) (2025)
- [LapaTrack-3D: 6 DoF pre-operative shape tracking for laparoscopic surgery](https://mlsanity.com/paper/2609.19954/) (2026)

## Abstract (arXiv)

Pose Graph Optimization involves the estimation of a set of poses from pairwise measurements and provides a formalization for many problems arising in mobile robotics and geometric computer vision. In this paper, we consider the case in which a subset of the measurements fed to pose graph optimization is spurious. Our first contribution is to develop robust estimators that can cope with heavy-tailed measurement noise, hence increasing robustness to the presence of outliers. Since the resulting estimators require solving nonconvex optimization problems, we further develop convex relaxations that approximately solve those problems via semidefinite programming. We then provide conditions under which the proposed relaxations are exact. Contrarily to existing approaches, our convex relaxations do not rely on the availability of an initial guess for the unknown poses, hence they are more suitable for setups in which such guess is not available (e.g., multi-robot localization, recovery after localization failure). We tested the proposed techniques in extensive simulations, and we show that some of the proposed relaxations are indeed tight (i.e., they solve the original nonconvex problem 10 exactly) and ensure accurate estimation in the face of a large number of outliers.