On the Tightness of Semidefinite Relaxations for Rotation Estimation
This work provides a theoretical understanding of the tightness of semidefinite relaxations for rotation estimation, which is important for researchers and practitioners relying on these methods in computer vision and robotics.
This paper investigates the empirical success of semidefinite relaxations for non-convex rotation estimation problems in computer vision and robotics. It introduces an algebraic geometry framework to analyze these relaxations, demonstrating that while some problem classes are always tight, there exist failure cases where the relaxation is not tight, even for a single rotation.
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.