We propose a general framework for group synchronization with adversarial corruption and sufficiently small noise. Specifically, we apply a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of group ratios and consequently infers the corrupted group ratios and solves the synchronization problem. 

We establish exact recovery and linear convergence guarantees for the proposed algorithm under a deterministic setting with adversarial corruption. These guarantees hold as long as the ratio of corrupted cycles per edge is bounded by a reasonable constant. We also establish the stability of the proposed procedure to sub-Gaussian noise. We further show that under a uniform corruption model, the recovery results are sharp in terms of an information-theoretic bound.

Yunpeng Shi is a Ph.D. candidate in the school of mathematics at the University of Minnesota, under the supervision of Prof. Gilad Lerman. He obtained his bachelor's degree from the University of Minnesota. He has been working on structure from motion (SfM) and its associated inverse problems. His current work is on robust group synchronization that has applications in 3D reconstruction, cryo-electron microscopy imaging, multi-graph matching, and community detection.