Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search: Tight or Not
Liangzu Peng, Mahyar Fazlyab, René Vidal
Abstract
"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 or not 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."
BibTeX
@inproceedings{eccv2022_semidefiniterela,
title = {Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search: Tight or Not},
author = {Liangzu Peng and Mahyar Fazlyab and René Vidal},
booktitle = {ECCV 2022},
year = {2022}
}