Robust Group Synchronization via Cycle-Edge Message Passing

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 show that under a uniform corruption model, the
recovery results are sharp in terms of an information-theoretic bound.
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.