# CLIPPER: Robust Data Association without an Initial Guess

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 60 references that are in the map.
- First posted on arXiv 11 Feb 2024.

## Builds on (most cited first, 18 of 18)

- [3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions](https://mlsanity.com/paper/1603.08182/) (2016)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates](https://mlsanity.com/paper/1903.08588/) (2019)
- [ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants](https://mlsanity.com/paper/2011.03659/) (2020)
- [CLIPPER: A Graph-Theoretic Framework for Robust Data Association](https://mlsanity.com/paper/2011.10202/) (2020)
- [SDRSAC: Semidefinite-Based Randomized Approach for Robust Point Cloud Registration without Correspondences](https://mlsanity.com/paper/1904.03483/) (2019)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models](https://mlsanity.com/paper/1810.11692/) (2018)
- [Convex Relaxations for Pose Graph Optimization with Outliers](https://mlsanity.com/paper/1801.02112/) (2018)
- [Deterministic Approximate Methods for Maximum Consensus Robust Fitting](https://mlsanity.com/paper/1710.10003/) (2017)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [A note on Probably Certifiably Correct algorithms](https://mlsanity.com/paper/1509.00824/) (2015)
- [Global Data Association for SLAM with 3D Grassmannian Manifold Objects](https://mlsanity.com/paper/2205.08556/) (2022)
- [GraffMatch: Global Matching of 3D Lines and Planes for Wide Baseline LiDAR Registration](https://mlsanity.com/paper/2212.12745/) (2022)
- [Group-k Consistent Measurement Set Maximization for Robust Outlier Detection](https://mlsanity.com/paper/2209.02658/) (2022)
- [Group-k consistent measurement set maximization via maximum clique over k-Uniform hypergraphs for robust multi-robot map merging](https://mlsanity.com/paper/2308.02674/) (2023)

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

- [Language-Grounded Hierarchical Planning and Execution with Multi-Robot 3D Scene Graphs](https://mlsanity.com/paper/2506.07454/) (2025)
- [Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis](https://mlsanity.com/paper/2508.15613/) (2025)
- [VISTA: Monocular Segmentation-Based Mapping for Appearance and View-Invariant Global Localization](https://mlsanity.com/paper/2507.11653/) (2025)

## Abstract (arXiv)

Identifying correspondences in noisy data is a critically important step in estimation processes. When an informative initial estimation guess is available, the data association challenge is less acute; however, the existence of a high-quality initial guess is rare in most contexts. We explore graph-theoretic formulations for data association, which do not require an initial estimation guess. Existing graph-theoretic approaches optimize over unweighted graphs, discarding important consistency information encoded in weighted edges, and frequently attempt to solve NP-hard problems exactly. In contrast, we formulate a new optimization problem that fully leverages weighted graphs and seeks the densest edge-weighted clique. We introduce two relaxations to this problem: a convex semidefinite relaxation which we find to be empirically tight, and a fast first-order algorithm called CLIPPER which frequently arrives at nearly-optimal solutions in milliseconds. When evaluated on point cloud registration problems, our algorithms remain robust up to at least 95% outliers while existing algorithms begin breaking down at 80% outliers. Code is available at https://mit-acl.github.io/clipper.