Georgia Institute of Technology College of Sciences

The problem of group synchronization asks to recover states of objects associated with group elements given possibly corrupted relative state measurements (or group ratios) between pairs of objects. 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. Two common groups in these problems are the rotation and symmetric groups. 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 first explain why the group cycle consistency information is essential for effectively solving group synchronization problems. We then 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 establish competitive theoretical results under a 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 two different problems that occur in structure from motion and involve the rotation and permutation groups.