# Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 53 references that are in the map.
- First posted on arXiv 21 Aug 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [3D Registration with Maximal Cliques](https://mlsanity.com/paper/2305.10854/) (2023)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration](https://mlsanity.com/paper/2203.14453/) (2022)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants](https://mlsanity.com/paper/2011.03659/) (2020)
- [A Purely Algebraic Justification of the Kabsch-Umeyama Algorithm](https://mlsanity.com/paper/1902.03138/) (2019)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Convex Relaxations for Pose Graph Optimization with Outliers](https://mlsanity.com/paper/1801.02112/) (2018)
- [One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers](https://mlsanity.com/paper/2006.06769/) (2020)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021)
- [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)
- [An Efficient Global Optimality Certificate for Landmark-Based SLAM](https://mlsanity.com/paper/2206.12961/) (2022)
- [An Overview of the Burer-Monteiro Method for Certifiable Robot Perception](https://mlsanity.com/paper/2410.00117/) (2024)
- [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024)
- [Minimizing a Sum of Clipped Convex Functions](https://mlsanity.com/paper/1910.12342/) (2019)
- [GMCR: Graph-based Maximum Consensus Estimation for Point Cloud Registration](https://mlsanity.com/paper/2303.04032/) (2023)

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

- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry](https://mlsanity.com/paper/2610.10408/) (2026)

## Abstract (arXiv)

Recent results showed that point cloud registration with given correspondences can be made robust to outlier rates of up to 95% using the truncated least squares (TLS) formulation. However, solving this combinatorial optimization problem to global optimality is challenging. Provably globally optimal approaches using semidefinite programming (SDP) relaxations take hundreds of seconds for 100 points. In this paper, we propose a novel linear time convex relaxation as well as a contractor method to speed up Branch and Bound (BnB). Our solver can register two 3D point clouds with 100 points to provable global optimality in less than half a second when the axis of rotation is provided. Although it currently cannot solve the full 6DoF problem, it is two orders of magnitude faster than the state-of-the-art SDP solver STRIDE when solving the rotation-only TLS problem. In addition to providing a formal proof for global optimality, we present empirical evidence of global optimality using adversarial instances with local minimas close to the global minimum.