Depth Descent Synchronization in $\mathrm{SO}(D)$
This addresses robust estimation in synchronization problems for applications like computer vision or sensor networks, with incremental improvements in handling adversarial outliers.
The paper tackles robust synchronization on the rotation group SO(D) in an adversarial corruption setting, developing a novel algorithm that exactly recovers underlying rotations up to an outlier fraction of 1/(D(D-1)+2), such as 1/4 for SO(2) and 1/8 for SO(3).
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.