# Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection

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

## Key facts

- Cited by 94 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2019.

## Built on by (most cited first, 30 of 94)

- [LaMAR: Benchmarking Localization and Mapping for Augmented Reality](https://mlsanity.com/paper/2210.10770/) (2022)
- [Semantics for Robotic Mapping, Perception and Interaction: A Survey](https://mlsanity.com/paper/2101.00443/) (2021)
- [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)
- [MULLS: Versatile LiDAR SLAM via Multi-metric Linear Least Square](https://mlsanity.com/paper/2102.03771/) (2021)
- [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)
- [Swarm-SLAM : Sparse Decentralized Collaborative Simultaneous Localization and Mapping Framework for Multi-Robot Systems](https://mlsanity.com/paper/2301.06230/) (2023)
- [A Single Correspondence Is Enough: Robust Global Registration to Avoid Degeneracy in Urban Environments](https://mlsanity.com/paper/2203.06612/) (2022)
- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021)
- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [KISS-Matcher: Fast and Robust Point Cloud Registration Revisited](https://mlsanity.com/paper/2409.15615/) (2024)
- [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)
- [Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging](https://mlsanity.com/paper/2103.08292/) (2021)
- [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)
- [TriVoC: Efficient Voting-based Consensus Maximization for Robust Point Cloud Registration with Extreme Outlier Ratios](https://mlsanity.com/paper/2111.00657/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023)
- [Efficient Reachability Analysis of Closed-Loop Systems with Neural Network Controllers](https://mlsanity.com/paper/2101.01815/) (2021)
- [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)
- [BUFFER-X: Towards Zero-Shot Point Cloud Registration in Diverse Scenes](https://mlsanity.com/paper/2503.07940/) (2025)
- [SG-Reg: Generalizable and Efficient Scene Graph Registration](https://mlsanity.com/paper/2504.14440/) (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)
- [Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms](https://mlsanity.com/paper/2302.07184/) (2023)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [RANSAC Back to SOTA: A Two-stage Consensus Filtering for Real-time 3D Registration](https://mlsanity.com/paper/2410.15682/) (2024)

## Abstract (arXiv)

Semidefinite Programming (SDP) and Sums-of-Squares (SOS) relaxations have led to certifiably optimal non-minimal solvers for several robotics and computer vision problems. However, most non-minimal solvers rely on least-squares formulations, and, as a result, are brittle against outliers. While a standard approach to regain robustness against outliers is to use robust cost functions, the latter typically introduce other non-convexities, preventing the use of existing non-minimal solvers. In this paper, we enable the simultaneous use of non-minimal solvers and robust estimation by providing a general-purpose approach for robust global estimation, which can be applied to any problem where a non-minimal solver is available for the outlier-free case. To this end, we leverage the Black-Rangarajan duality between robust estimation and outlier processes (which has been traditionally applied to early vision problems), and show that graduated non-convexity (GNC) can be used in conjunction with non-minimal solvers to compute robust solutions, without requiring an initial guess. Although GNC's global optimality cannot be guaranteed, we demonstrate the empirical robustness of the resulting robust non-minimal solvers in applications, including point cloud and mesh registration, pose graph optimization, and image-based object pose estimation (also called shape alignment). Our solvers are robust to 70-80% of outliers, outperform RANSAC, are more accurate than specialized local solvers, and faster than specialized global solvers. We also propose the first certifiably optimal non-minimal solver for shape alignment using SOS relaxation.