Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search
This work addresses robustness in 3D rotation alignment for applications like computer vision, but it is incremental as it builds on prior theoretical analysis.
The paper tackles the problem of robust rotation search by analyzing the tightness of semidefinite relaxations for truncated least-squares, deriving conditions based on noise level, truncation parameters, and outlier distribution, and providing a concise proof for the noiseless and outlier-free case.
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.