Depth Descent Synchronization in $\mathrm{SO}(D)$

Abstract

We give robust recovery results for synchronization on the rotation group, $\mathrm{SO}(D)$. In particular, we consider an adversarial corruption setting, where a limited percentage of the observations are arbitrarily corrupted. We give a novel algorithm that exploits Tukey depth in the tangent space, which exactly recovers the underlying rotations up to an outlier percentage of $1/(D(D-1)+2)$. This corresponds to an outlier fraction of $1/4$ for $\mathrm{SO}(2)$ and $1/8$ for $\mathrm{SO}(3)$. In the case of $D=2$, we demonstrate that a variant of this algorithm converges linearly to the ground truth rotations. We finish by discussing this result in relation to a simpler nonconvex energy minimization framework based on least absolute deviations, which exhibits spurious fixed points.

22 pages, 3 figures

References in corpus (10)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• An Overview of Robust Subspace Recovery
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Robust Estimation and Generative Adversarial Nets
• Robust Subspace Recovery with Adversarial Outliers
• Robust Group Synchronization via Cycle-Edge Message Passing
• Exact Minimax Estimation for Phase Synchronization
• Exact Camera Location Recovery by Least Unsquared Deviations