# Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 64 references that are in the map.
- First posted on arXiv 18 Jul 2022.

## Builds on (most cited first, 30 of 31)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Guaranteed Outlier Removal for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/1711.10209/) (2017)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019)
- [Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications](https://mlsanity.com/paper/2007.15109/) (2020)
- [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)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [Convex Relaxations for Pose Graph Optimization with Outliers](https://mlsanity.com/paper/1801.02112/) (2018)
- [Lagrangian Duality in 3D SLAM: Verification Techniques and Optimal Solutions](https://mlsanity.com/paper/1506.00746/) (2015)
- [Global registration of multiple point clouds using semidefinite programming](https://mlsanity.com/paper/1306.5226/) (2013)
- [Distributed Certifiably Correct Pose-Graph Optimization](https://mlsanity.com/paper/1911.03721/) (2019)
- [An Efficient Solution to Non-Minimal Case Essential Matrix Estimation](https://mlsanity.com/paper/1903.09067/) (2019)
- [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)
- [On the local stability of semidefinite relaxations](https://mlsanity.com/paper/1710.04287/) (2017)
- [CvxPnPL: A Unified Convex Solution to the Absolute Pose Estimation Problem from Point and Line Correspondences](https://mlsanity.com/paper/1907.10545/) (2019)
- [Certifiable Relative Pose Estimation](https://mlsanity.com/paper/2003.13732/) (2020)
- [A convex relaxation to compute the nearest structured rank deficient matrix](https://mlsanity.com/paper/1904.09661/) (2019)
- [Certifiably Optimal Monocular Hand-Eye Calibration](https://mlsanity.com/paper/2005.08298/) (2020)
- [On the Tightness of Semidefinite Relaxations for Rotation Estimation](https://mlsanity.com/paper/2101.02099/) (2021)
- [Certifiably Globally Optimal Extrinsic Calibration from Per-Sensor Egomotion](https://mlsanity.com/paper/1809.03554/) (2018)
- [Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras](https://mlsanity.com/paper/2101.08524/) (2021)
- [Non-iterative rigid 2D/3D point-set registration using semidefinite programming](https://mlsanity.com/paper/1501.00630/) (2015)
- [Near-Optimal Bounds for Generalized Orthogonal Procrustes Problem via Generalized Power Method](https://mlsanity.com/paper/2112.13725/) (2021)
- [Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision](https://mlsanity.com/paper/1909.12034/) (2019)

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

- [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)

## Abstract (arXiv)

The rotation search problem aims to find a 3D rotation that best aligns a given number of point pairs. To induce robustness against outliers for rotation search, prior work considers truncated least-squares (TLS), which is a non-convex optimization problem, and its semidefinite relaxation (SDR) as a tractable alternative. Whether this SDR is theoretically tight in the presence of noise, outliers, or both has remained largely unexplored. We derive conditions that characterize the tightness of this SDR, showing that the tightness depends on the noise level, the truncation parameters of TLS, and the outlier distribution (random or clustered). In particular, we give a short proof for the tightness in the noiseless and outlier-free case, as opposed to the lengthy analysis of prior work.