# Estimation Contracts for Outlier-Robust Geometric Perception

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 116 references that are in the map.
- First posted on arXiv 22 Aug 2022.

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

- [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)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Guaranteed Outlier Removal for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/1711.10209/) (2017)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019)
- [Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications](https://mlsanity.com/paper/2007.15109/) (2020)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [Beyond Gr"obner Bases: Basis Selection for Minimal Solvers](https://mlsanity.com/paper/1803.04360/) (2018)
- [Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models](https://mlsanity.com/paper/1810.11692/) (2018)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Convex Relaxations for Pose Graph Optimization with Outliers](https://mlsanity.com/paper/1801.02112/) (2018)

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

- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [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)
- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [Certifiably Optimal Anisotropic Rotation Averaging](https://mlsanity.com/paper/2503.07353/) (2025)
- [Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing](https://mlsanity.com/paper/2310.15549/) (2023)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [Global Truncated Loss Minimization for Robust and Threshold-Resilient Geometric Estimation](https://mlsanity.com/paper/2603.14796/) (2026)

## Abstract (arXiv)

Outlier-robust estimation is a fundamental problem and has been extensively investigated by statisticians and practitioners. The last few years have seen a convergence across research fields towards "algorithmic robust statistics", which focuses on developing tractable outlier-robust techniques for high-dimensional estimation problems. Despite this convergence, research efforts across fields have been mostly disconnected from one another. This monograph bridges recent work on certifiable outlier-robust estimation for geometric perception in robotics and computer vision with parallel work in robust statistics. In particular, we adapt and extend recent results on robust linear regression (applicable to the low-outlier regime with << 50% outliers) and list-decodable regression (applicable to the high-outlier regime with >> 50% outliers) to the setup commonly found in robotics and vision, where (i) variables (e.g., rotations, poses) belong to a non-convex domain, (ii) measurements are vector-valued, and (iii) the number of outliers is not known a priori. The emphasis here is on performance guarantees: rather than proposing radically new algorithms, we provide conditions on the input measurements under which modern estimation algorithms (possibly after small modifications) are guaranteed to recover an estimate close to the ground truth in the presence of outliers. These conditions are what we call an "estimation contract". Besides the proposed extensions of existing results, we believe the main contributions of this monograph are (i) to unify parallel research lines by pointing out commonalities and differences, (ii) to introduce advanced material (e.g., sum-of-squares proofs) in an accessible and self-contained presentation for the practitioner, and (iii) to point out a few immediate opportunities and open questions in outlier-robust geometric perception.