# A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers

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

## Key facts

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

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

- [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)
- [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)
- [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)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [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)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Dynamical Pose Estimation](https://mlsanity.com/paper/2103.06182/) (2021)
- [Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras](https://mlsanity.com/paper/2101.08524/) (2021)
- [From Correspondences to Pose: Non-minimal Certifiably Optimal Relative Pose without Disambiguation](https://mlsanity.com/paper/2312.05995/) (2023)
- [Consensus Maximisation Using Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2103.04200/) (2021)
- [IRON: Invariant-based Highly Robust Point Cloud Registration](https://mlsanity.com/paper/2103.04357/) (2021)
- [Semidefinite Relaxations for Robust Multiview Triangulation](https://mlsanity.com/paper/2301.11431/) (2023)
- [FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator](https://mlsanity.com/paper/2409.13978/) (2024)
- [Spatiotemporal Multi-Camera Calibration using Freely Moving People](https://mlsanity.com/paper/2502.12546/) (2025)
- [Category-Level Object Shape and Pose Estimation in Less Than a Millisecond](https://mlsanity.com/paper/2509.18979/) (2025)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Multi-to-Single Knowledge Distillation for Point Cloud Semantic Segmentation](https://mlsanity.com/paper/2304.14800/) (2023)
- [DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming](https://mlsanity.com/paper/2603.25442/) (2026)
- [Robust Point Matching with Distance Profiles](https://mlsanity.com/paper/2312.12641/) (2023)
- [Correspondence-Free Fast and Robust Spherical Point Pattern Registration](https://mlsanity.com/paper/2508.02339/) (2025)
- [Uncertainty Quantification for Visual Object Pose Estimation: S-Lemma Ellipsoidal Bounds](https://mlsanity.com/paper/2511.21666/) (2025)
- [ICOS: Efficient and Highly Robust Rotation Search and Point Cloud Registration with Correspondences](https://mlsanity.com/paper/2104.14763/) (2021)
- [Cryo-forum: A framework for orientation recovery with uncertainty measure with the application in cryo-EM image analysis](https://mlsanity.com/paper/2307.09847/) (2023)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [Fast, Robust, Permutation-and-Sign Invariant SO(3) Pattern Alignment](https://mlsanity.com/paper/2512.00659/) (2025)

## Abstract (arXiv)

The Wahba problem, also known as rotation search, seeks to find the best rotation to align two sets of vector observations given putative correspondences, and is a fundamental routine in many computer vision and robotics applications. This work proposes the first polynomial-time certifiably optimal approach for solving the Wahba problem when a large number of vector observations are outliers. Our first contribution is to formulate the Wahba problem using a Truncated Least Squares (TLS) cost that is insensitive to a large fraction of spurious correspondences. The second contribution is to rewrite the problem using unit quaternions and show that the TLS cost can be framed as a Quadratically-Constrained Quadratic Program (QCQP). Since the resulting optimization is still highly non-convex and hard to solve globally, our third contribution is to develop a convex Semidefinite Programming (SDP) relaxation. We show that while a naive relaxation performs poorly in general, our relaxation is tight even in the presence of large noise and outliers. We validate the proposed algorithm, named QUASAR (QUAternion-based Semidefinite relAxation for Robust alignment), in both synthetic and real datasets showing that the algorithm outperforms RANSAC, robust local optimization techniques, global outlier-removal procedures, and Branch-and-Bound methods. QUASAR is able to compute certifiably optimal solutions (i.e. the relaxation is exact) even in the case when 95% of the correspondences are outliers.