"Robust Synchronization via Cycle Consistency Inference
We propose a strategy for improving the existing methods for solving synchronization problems that arise from various computer vision tasks. Specifically, our strategy identifies severely corrupted relative measurements based on cycle consistency information. To the best of our knowledge, this paper provides the first exact recovery guarantees using cycle consistency information. This result holds for a noiseless but corrupted setting as long as the ratio of corrupted cycles per edge is sufficiently small. It further guarantees linear convergence to the desired solution. We also establish stability of the proposed algorithm to sub-Gaussian noise.