# On the Tightness of Semidefinite Relaxations for Rotation Estimation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 46 references that are in the map.
- First posted on arXiv 6 Jan 2021.

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

- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [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)
- [A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints](https://mlsanity.com/paper/1506.00575/) (2015)
- [On the local stability of semidefinite relaxations](https://mlsanity.com/paper/1710.04287/) (2017)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [Certifiably Globally Optimal Extrinsic Calibration from Per-Sensor Egomotion](https://mlsanity.com/paper/1809.03554/) (2018)
- [A bounded degree SOS hierarchy for polynomial optimization](https://mlsanity.com/paper/1501.06126/) (2015)
- [Guaranteed Globally Optimal Planar Pose Graph and Landmark SLAM via Sparse-Bounded Sums-of-Squares Programming](https://mlsanity.com/paper/1809.07744/) (2018)
- [CPL-SLAM: Efficient and Certifiably Correct Planar Graph-Based SLAM Using the Complex Number Representation](https://mlsanity.com/paper/2007.06708/) (2020)
- [The Geometry of SDP-Exactness in Quadratic Optimization](https://mlsanity.com/paper/1804.01796/) (2018)
- [Pose Proposal Critic: Robust Pose Refinement by Learning Reprojection Errors](https://mlsanity.com/paper/2005.06262/) (2020)

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

- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Category-Level Object Shape and Pose Estimation in Less Than a Millisecond](https://mlsanity.com/paper/2509.18979/) (2025)
- [Newton-PnP: Real-time Visual Navigation for Autonomous Toy-Drones](https://mlsanity.com/paper/2203.02686/) (2022)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Convex Relaxation for Solving Large-Margin Classifiers in Hyperbolic Space](https://mlsanity.com/paper/2405.17198/) (2024)
- [Accelerating Outlier-robust Rotation Estimation by Stereographic Projection](https://mlsanity.com/paper/2502.06337/) (2025)

## Abstract (arXiv)

Why is it that semidefinite relaxations have been so successful in numerous applications in computer vision and robotics for solving non-convex optimization problems involving rotations? In studying the empirical performance we note that there are few failure cases reported in the literature, in particular for estimation problems with a single rotation, motivating us to gain further theoretical understanding. A general framework based on tools from algebraic geometry is introduced for analyzing the power of semidefinite relaxations of problems with quadratic objective functions and rotational constraints. Applications include registration, hand-eye calibration and rotation averaging. We characterize the extreme points, and show that there exist failure cases for which the relaxation is not tight, even in the case of a single rotation. We also show that some problem classes are always tight given an appropriate parametrization. Our theoretical findings are accompanied with numerical simulations, providing further evidence and understanding of the results.