Higher-order group synchronization

Abstract Group synchronization is the problem of determining reliable global estimates from noisy local measurements on networks. The typical task for group synchronization is to assign elements of a group to the nodes of a graph in a way that respects group elements given on the edges which encode information about local pairwise relationships between the nodes. In this paper, we introduce a novel higher-order group synchronization problem which is formulated on a hypergraph and seeks to synchronize higher-order local measurements along hyperedges in order to obtain global estimates on the nodes. Higher-order group synchronization is motivated by applications to computer vision, image processing, robotics, and community detection, among other domains. First, we define the problem of higher-order group synchronization and discuss its mathematical foundations. Specifically, we give necessary and sufficient conditions for synchronizability which establish the importance of cycle consistency in higher-order group synchronization. Next, we propose the first computational framework for general higher-order group synchronization; it acts globally and directly on higher-order measurements via a message passing algorithm. We derive theoretical guarantees for our framework, including convergence analyses in the presence of outliers and noise. Finally, we demonstrate potential advantages of our method through numerical experiments. In particular, we show that in certain cases our higher-order method applied to rotational and angular synchronization outperforms standard pairwise synchronization methods and is more robust to outliers. We also show that our method has comparable performance on simulated cryo-electron microscopy (cryo-EM) data compared to a standard cryo-EM reconstruction package.