Abstract
Outlier-robust estimation is a fundamental problem in robotics and computer vision, where sensor data is frequently corrupted by mis-detections or dynamic environments. While "algorithmic robust statistics" has emerged as a powerful framework for high-dimensional estimation, its application to geometric perception has remained largely disconnected from mainstream robotics research. This paper bridges this gap by adapting results from robust linear regression and list-decodable regression to the specific constraints of robotics, such as non-convex domains (e.g., rotations and poses) and vector-valued measurements. We introduce the concept of "estimation contracts"—mathematical conditions on input measurements under which modern algorithms are guaranteed to recover ground-truth estimates. By unifying these research lines and utilizing Sum-of-Squares (SoS) proofs, we provide a framework that handles both low-outlier regimes and extreme cases where outliers exceed 50% of the data.
Introduction
In geometric perception, the goal is to estimate spatial models—such as the 3D position of a vehicle or the orientation of a camera—from sensor observations. However, real-world data is rarely clean. Neural network feature matchers may produce false correspondences, and moving objects can be mistaken for static landmarks. These outliers cause standard estimation techniques like Least Squares to fail catastrophically.
While the robotics community has developed various robust alternatives, including Truncated Least Squares (TLS) and Consensus Maximization, these problems are inherently NP-hard. Practitioners often rely on heuristics like RANSAC or "certifiable" solvers that verify an answer post-computation. This work shifts the focus toward a priori guarantees: defining the specific conditions under which an algorithm is guaranteed to succeed before it is even executed.
Theoretical Framework: Estimation Contracts
The core contribution of this work is the "estimation contract." This is a set of conditions—specifically certifiable hypercontractivity and anti-concentration—that, if satisfied by the inlier data, ensure a solver will recover an estimate close to the ground truth.
To derive these contracts, we utilize two primary mathematical tools:
- Lasserre’s Hierarchy of Moment Relaxations: This framework transforms non-convex polynomial optimization problems into tractable Semidefinite Programs (SDP) that can be solved in polynomial time.
- Sum-of-Squares (SoS) Proofs: A modern proof system used to establish the robustness of these relaxations.
By rewriting robotics problems (such as rotation search and point cloud registration) as linear models over basic semi-algebraic sets, we allow these complex geometric tasks to inherit the powerful theoretical guarantees found in the statistics literature.
Handling High-Outlier Regimes
Traditional robust estimators typically break down when outliers exceed 50% of the dataset. To address this, we introduce List-Decodable Regression to the robotics context. In scenarios with 80% or 90% outliers, it is mathematically impossible to identify a single correct model with certainty. Instead, list-decodable algorithms return a small set of candidate models, guaranteeing that at least one is highly accurate.
We propose SLIDE (Sparse LIst-Decodable Estimation), a practical variant of this approach. While full theoretical SoS proofs often require computationally expensive high-order relaxations, SLIDE utilizes a "sparse" order-2 relaxation. This approach is significantly faster and capable of identifying multiple valid models simultaneously—for instance, tracking the motion of several distinct objects in a single scene.
Experimental Validation
The theoretical framework was validated using both synthetic and real-world data:
- Synthetic Benchmarks: In simulations with 80% to 90% adversarial outliers, the SLIDE algorithm consistently recovered ground-truth rotations within a few degrees, whereas standard robust methods failed.
- PASSTA Dataset: Using real-world image stitching data, we tested the estimation of rotations between camera frames using SURF features. Numerical analysis confirmed that "certifiable hypercontractivity"—the key theoretical requirement for our contracts—is indeed satisfied by real-world feature matching data.
Discussion and Future Work
While this work provides a rigorous foundation for robust perception, several challenges remain. The computational overhead of solving SDPs is currently too high for real-time, high-frequency robotics applications like drone navigation. Furthermore, there is a persistent "theory-practice gap": empirical results show that low-order relaxations (order-2) work remarkably well, even though current SoS proofs often require higher-order relaxations (order-4 or 6) to guarantee success.
Future research will focus on developing specialized, faster solvers and tightening theoretical bounds to include the "rounding" step—the process of projecting an abstract estimate back onto a valid geometric manifold (e.g., ensuring a matrix is a valid rotation). By bridging the gap between algorithmic statistics and robotics, we move closer to autonomous systems that can certifiably navigate the messiness of the real world.
Summary updated