Certifiably Optimal Robust Angular Synchronization

Rotation averaging on the circle, equivalently robust angular synchronization, underlies a wide range of geometric estimation problems, for example, gravity-aligned Structure-from-Motion, multi-way point-cloud registration, and in-plane alignment in single-particle cryo-electron microscopy. We present the first algorithm that certifiably solves the robust maximum-consensus formulation of this problem to global optimality. Our approach discretises the circle into uniform bins, formulates a pairwise Markov random field and solves it via branch-and-bound with two key novelties: an ICM-guided label-pruning rule that collapses the branching factor to a handful of candidates, and a node-constrained relaxation bound orders of magnitude tighter than the standard per-edge bound. Together, they reduce the search from millions of nodes to a few hundred on typical instances. On all tested problems, the algorithm terminates with a proof of global optimality, typically in a few seconds. Across synthetic graphs and three real-world domains – image-based SfM on IMC 2023/2024, multi-way LiDAR point-cloud registration on KITTI and NSS, and cryo-EM angular synchronization on EMPIAR-10166 – the certified solution achieves sub-degree accuracy at outlier rates where other baselines fail. Our code will be made publicly available.