Robust Group Synchronization via Cycle-Edge Message Passing
The problem of group synchronization asks to recover states of objects associated with group elements, such as rotations, given possibly corrupted relative state measurements (or group ratios) between pairs of objects. It gives rise to a graph with measured group ratios along its edges. This problem arises in important data-related tasks, such as structure from motion, simultaneous localization and mapping, Cryo-EM, community detection and sensor network localization. We propose a general framework for group synchronization with compact groups. The main part of the talk discusses a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of group ratios. Under our mathematical model of adversarial corruption, it can be used to infer the corrupted group ratios and thus to solve the synchronization problem. We establish exact recovery and linear convergence guarantees for the proposed message passing procedure under a deterministic setting with adversarial corruption. We also establish the stability of the proposed procedure to sub-Gaussian noise. We further demonstrate results for the common uniform corruption model. Finally, we discuss the MPLS (Message Passing Least Squares), or Minneapolis, framework for solving real scenarios with high levels of corruption and noise and with nontrivial scenarios of corruption. We demonstrate state-of-the-art results for rotation synchronization in the context of structure from motion.