# Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 125 references that are in the map.
- First posted on arXiv 7 Sep 2021.

## Builds on (most cited first, 30 of 45)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [A General and Adaptive Robust Loss Function](https://mlsanity.com/paper/1701.03077/) (2017)
- [The ApolloScape Open Dataset for Autonomous Driving and its Application](https://mlsanity.com/paper/1803.06184/) (2018)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [Graph-Cut RANSAC](https://mlsanity.com/paper/1706.00984/) (2017)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [HomebrewedDB: RGB-D Dataset for 6D Pose Estimation of 3D Objects](https://mlsanity.com/paper/1904.03167/) (2019)
- [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)
- [Guaranteed Outlier Removal for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/1711.10209/) (2017)
- [Satellite Pose Estimation with Deep Landmark Regression and Nonlinear Pose Refinement](https://mlsanity.com/paper/1908.11542/) (2019)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates](https://mlsanity.com/paper/1903.08588/) (2019)
- [ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants](https://mlsanity.com/paper/2011.03659/) (2020)
- [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019)
- [GSNet: Joint Vehicle Pose and Shape Reconstruction with Geometrical and Scene-aware Supervision](https://mlsanity.com/paper/2007.13124/) (2020)
- [Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications](https://mlsanity.com/paper/2007.15109/) (2020)
- [Self-supervised Geometric Perception](https://mlsanity.com/paper/2103.03114/) (2021)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models](https://mlsanity.com/paper/1810.11692/) (2018)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Pose Estimation for Non-Cooperative Rendezvous Using Neural Networks](https://mlsanity.com/paper/1906.09868/) (2019)
- [Convex Relaxations for Pose Graph Optimization with Outliers](https://mlsanity.com/paper/1801.02112/) (2018)
- [One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers](https://mlsanity.com/paper/2006.06769/) (2020)
- [Global registration of multiple point clouds using semidefinite programming](https://mlsanity.com/paper/1306.5226/) (2013)
- [In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction from 2D Landmarks](https://mlsanity.com/paper/1911.11924/) (2019)
- [An Efficient Solution to Non-Minimal Case Essential Matrix Estimation](https://mlsanity.com/paper/1903.09067/) (2019)
- [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021)
- [TSSOS: A Moment-SOS hierarchy that exploits term sparsity](https://mlsanity.com/paper/1912.08899/) (2019)

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

- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Training](https://mlsanity.com/paper/2206.11215/) (2022)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023)
- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [Efficient and Robust Point Cloud Registration via Heuristics-guided Parameter Search](https://mlsanity.com/paper/2404.06155/) (2024)
- [Building Rome with Convex Optimization](https://mlsanity.com/paper/2502.04640/) (2025)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [Monitoring of Perception Systems: Deterministic, Probabilistic, and Learning-based Fault Detection and Identification](https://mlsanity.com/paper/2205.10906/) (2022)
- [Towards Robust Probabilistic Modeling on SO(3) via Rotation Laplace Distribution](https://mlsanity.com/paper/2305.10465/) (2023)
- [Robust Fitting on a Gate Quantum Computer](https://mlsanity.com/paper/2409.02006/) (2024)
- [Robustness Certification of Visual Perception Models via Camera Motion Smoothing](https://mlsanity.com/paper/2210.04625/) (2022)
- [Semidefinite Relaxations for Robust Multiview Triangulation](https://mlsanity.com/paper/2301.11431/) (2023)
- [Certifiably Optimal Anisotropic Rotation Averaging](https://mlsanity.com/paper/2503.07353/) (2025)
- [Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis](https://mlsanity.com/paper/2508.15613/) (2025)
- [A Probabilistic Relaxation of the Two-Stage Object Pose Estimation Paradigm](https://mlsanity.com/paper/2306.00892/) (2023)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [SNAP: A Self-Consistent Agreement Principle with Application to Robust Computation](https://mlsanity.com/paper/2602.02013/) (2026)
- [Global Truncated Loss Minimization for Robust and Threshold-Resilient Geometric Estimation](https://mlsanity.com/paper/2603.14796/) (2026)
- [Triangulation-Free Bundle Adjustment with Graduated Non-Convexity for Camera Pose Refinement from Coarse Priors](https://mlsanity.com/paper/2608.21008/) (2026)

## Abstract (arXiv)

We propose the first general and scalable framework to design certifiable algorithms for robust geometric perception in the presence of outliers. Our first contribution is to show that estimation using common robust costs, such as truncated least squares (TLS), maximum consensus, Geman-McClure, Tukey's biweight, among others, can be reformulated as polynomial optimization problems (POPs). By focusing on the TLS cost, our second contribution is to exploit sparsity in the POP and propose a sparse semidefinite programming (SDP) relaxation that is much smaller than the standard Lasserre's hierarchy while preserving empirical exactness, i.e., the SDP recovers the optimizer of the nonconvex POP with an optimality certificate. Our third contribution is to solve the SDP relaxations at an unprecedented scale and accuracy by presenting STRIDE, a solver that blends global descent on the convex SDP with fast local search on the nonconvex POP. Our fourth contribution is an evaluation of the proposed framework on six geometric perception problems including single and multiple rotation averaging, point cloud and mesh registration, absolute pose estimation, and category-level object pose and shape estimation. Our experiments demonstrate that (i) our sparse SDP relaxation is empirically exact with up to 60%-90% outliers across applications; (ii) while still being far from real-time, STRIDE is up to 100 times faster than existing SDP solvers on medium-scale problems, and is the only solver that can solve large-scale SDPs with hundreds of thousands of constraints to high accuracy; (iii) STRIDE safeguards existing fast heuristics for robust estimation (e.g., RANSAC or Graduated Non-Convexity), i.e., it certifies global optimality if the heuristic estimates are optimal, or detects and allows escaping local optima when the heuristic estimates are suboptimal.