# Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2020.

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

- [Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems](https://mlsanity.com/paper/2106.14386/) (2021)
- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [Self-supervised Geometric Perception](https://mlsanity.com/paper/2103.03114/) (2021)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021)
- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems](https://mlsanity.com/paper/2109.12343/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [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)
- [Dynamical Pose Estimation](https://mlsanity.com/paper/2103.06182/) (2021)
- [Semidefinite Relaxations for Robust Multiview Triangulation](https://mlsanity.com/paper/2301.11431/) (2023)
- [Graph-based Global Robot Localization Informing Situational Graphs with Architectural Graphs](https://mlsanity.com/paper/2303.02076/) (2023)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization](https://mlsanity.com/paper/2311.08745/) (2023)
- [Correspondence-Free Fast and Robust Spherical Point Pattern Registration](https://mlsanity.com/paper/2508.02339/) (2025)
- [Outlier-Robust Geometric Perception: A Novel Thresholding-Based Estimator with Intra-Class Variance Maximization](https://mlsanity.com/paper/2204.01324/) (2022)
- [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)
- [Preserve, Then Resolve: Many-to-Many Association and Robust Estimation with General-Purpose Visual Features](https://mlsanity.com/paper/2604.23670/) (2026)
- [Efficient and Robust Absolute Pose Estimation via Gravity-Prior-Driven Transformation Decoupling and Pose Refinement](https://mlsanity.com/paper/2609.00713/) (2026)

## Abstract (arXiv)

Nonlinear estimation in robotics and vision is typically plagued with outliers due to wrong data association, or to incorrect detections from signal processing and machine learning methods. This paper introduces two unifying formulations for outlier-robust estimation, Generalized Maximum Consensus (G-MC) and Generalized Truncated Least Squares (G-TLS), and investigates fundamental limits, practical algorithms, and applications. Our first contribution is a proof that outlier-robust estimation is inapproximable: in the worst case, it is impossible to (even approximately) find the set of outliers, even with slower-than-polynomial-time algorithms (particularly, algorithms running in quasi-polynomial time). As a second contribution, we review and extend two general-purpose algorithms. The first, Adaptive Trimming (ADAPT), is combinatorial, and is suitable for G-MC; the second, Graduated Non-Convexity (GNC), is based on homotopy methods, and is suitable for G-TLS. We extend ADAPT and GNC to the case where the user does not have prior knowledge of the inlier-noise statistics (or the statistics may vary over time) and is unable to guess a reasonable threshold to separate inliers from outliers (as the one commonly used in RANSAC). We propose the first minimally tuned algorithms for outlier rejection, that dynamically decide how to separate inliers from outliers. Our third contribution is an evaluation of the proposed algorithms on robot perception problems: mesh registration, image-based object detection (shape alignment), and pose graph optimization. ADAPT and GNC execute in real-time, are deterministic, outperform RANSAC, and are robust up to 80-90% outliers. Their minimally tuned versions also compare favorably with the state of the art, even though they do not rely on a noise bound for the inliers.