Estimation Contracts for Outlier-Robust Geometric Perception

Luca Carlone

TL;DR

This monograph provides "estimation contracts"—mathematical guarantees that ensure outlier-robust algorithms can recover ground-truth geometric models (like poses and rotations) even when data is heavily corrupted. By bridging robotics research with "algorithmic robust statistics," it introduces a unified framework that handles both low-outlier regimes and extreme cases where over 50% of the data are outliers.

What Problem Does This Paper Address?

In robotics and computer vision, "geometric perception" is the task of estimating models (like the 3D position of a car or the rotation of a camera) from sensor data. However, sensor data is messy. Neural networks might mis-detect features, or a moving object might be mistaken for a static background. These incorrect data points are outliers.

Standard estimation techniques (like Least Squares) fail catastrophically in the presence of even a few outliers. While researchers have developed robust alternatives—like Truncated Least Squares (TLS) or Consensus Maximization (MC)—these problems are technically NP-hard. Robotics practitioners often rely on heuristics (like RANSAC) or "certifiable" solvers that check if an answer is right after computing it.

The gap this paper fills is providing a priori guarantees. It asks: Under what conditions on the input data can we guarantee that our algorithms will succeed before we even run them?

Methods

The paper utilizes two heavy-duty mathematical tools:

  1. Lasserre’s Hierarchy of Moment Relaxations: This technique transforms hard, 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 derive "estimation contracts." These contracts are conditions—specifically certifiable hypercontractivity and anti-concentration—that, if satisfied by the inlier data, ensure the solver will recover an estimate close to the ground truth.

The author adapts these tools from the field of robust statistics (which usually deals with simple linear regression) to the complex, manifold-constrained world of robotics (where variables live on non-convex sets like rotations and poses).

Datasets

The theoretical results are validated using:

  • Synthetic Data: Randomly generated 3D points on a unit sphere, corrupted with varying levels of noise and adversarial outliers.
  • PASSTA Dataset: A real-world dataset used for image stitching. The paper uses SURF features from real images to test how well the algorithms can estimate the rotation between camera frames in a practical setting.

Key Insights and Ideas

  • Geometric Perception as Linear Regression: A core insight is that many robotics problems (rotation search, point cloud registration, pose estimation) can be rewritten as linear models over "basic semi-algebraic sets." This allows robotics to inherit powerful theoretical tools from the statistics community.
  • The 50% Outlier Barrier: Most traditional robust estimators fail when more than 50% of the data are outliers. The paper introduces List-Decodable Regression to the robotics community. Instead of returning one answer (which might be wrong), the algorithm returns a small list of candidates, guaranteeing that at least one is highly accurate.
  • SLIDE (Sparse LIst-Decodable Estimation): The paper proposes a practical variant of list-decodable estimation. While the full theory requires computationally expensive high-order relaxations, the author shows that a "sparse" order-2 relaxation is both fast enough to be useful and surprisingly accurate.
  • Multi-Hypothesis Recovery: A standout feature of the list-decodable approach is its ability to find multiple valid models simultaneously—for example, identifying the motion of two different objects in a scene at once.

Key Results

  • Low-Outlier Regime (<50%): The paper provides the first general performance bounds for popular robotics relaxations (TLS and MC), showing they are robust if the data is "anti-concentrated" (meaning the measurements are diverse enough to uniquely define the model).
  • High-Outlier Regime (>50%): In experiments with 80% to 90% outliers, the proposed SLIDE algorithm consistently recovered the ground truth rotation within a few degrees, whereas standard robust methods failed completely.
  • Practicality of Assumptions: Numerical tests on the PASSTA dataset revealed that "certifiable hypercontractivity"—a key theoretical requirement—is actually satisfied by real-world feature matching data, suggesting the theory is grounded in reality.

Limitations and Future Work

  • Computational Overhead: Even with "sparse" relaxations, solving SDPs is currently too slow for high-frequency robotics tasks (like 20Hz drone navigation). The author notes that specialized solvers are needed to reach real-time performance.
  • The Theoretical Gap: There is still a gap between theory and practice. The SoS proofs often require high-order relaxations (order 4 or 6) for a guarantee, but in practice, order-2 relaxations work perfectly. Explaining why these lower-order versions are so effective remains an open question.
  • Rounding: The current contracts don't fully account for the final step of "projecting" an estimate back onto a manifold (e.g., making sure a matrix is a valid rotation). Tightening the bounds to include this step is a suggested next step.

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”. The monograph also provides numerical experiments to shed light on the applicability of the theoretical results and to showcase the potential of list-decodable regression algorithms in geometric perception. 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},
}

Loading related content...

Figure