Estimation Contracts for Outlier-Robust Geometric Perception

Luca Carlone

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:

  1. 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.
  2. 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

Abstract

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.
BibTeX
@inproceedings{carlone2023estimation,
  author = {Luca Carlone},
  title = {{Estimation Contracts for Outlier-Robust Geometric Perception}},
  booktitle = {Found. Trends Robotics},
  year = {2023},
  url = {https://openreview.net/forum?id=nS3PoE9ZTQ},
}
Figure