Depth Descent Synchronization in
arXiv:2002.05299
Abstract
We give robust recovery results for synchronization on the rotation group, . 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 . This corresponds to an outlier fraction of for and for . In the case of , 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.
arXiv comment22 pages, 3 figures
References in corpus (15)
- Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Matrix Completion has No Spurious Local Minimum
- Nonconvex phase synchronization
- An Overview of Robust Subspace Recovery
- Gradient Descent Converges to Minimizers
- On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
- Fast, Robust and Non-convex Subspace Recovery
- A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
- 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