FAST-Sync: Fast Group Synchronization for Any Matrix Lie Group

Abstract

Group synchronization (GS) is the problem of estimating a set of <inline-formula><tex-math notation="LaTeX">$N$</tex-math></inline-formula> unknown elements <inline-formula><tex-math notation="LaTeX">$g_{1},\ldots\,, g_{N} \in \mathcal {G}$</tex-math></inline-formula> in a group <inline-formula><tex-math notation="LaTeX">$\mathcal {G}$</tex-math></inline-formula>, given noisy measurements of a subset of their pairwise ratios <inline-formula><tex-math notation="LaTeX">$g_{i}^{-1} g_{j}$</tex-math></inline-formula>. GS problems lie at the core of many state estimation tasks in robotics and computer vision, including 3D vision, robotic mapping, inertial navigation, and molecular reconstruction. Unfortunately, GS problems are typically both high-dimensional and non-convex, and therefore hard to solve in general. In this paper, we present <italic>Fast-Sync</italic>, a fast linear approximation method for GS that is suitable for initializing local manifold-based optimizers or certifiable global methods. Our approach generalizes chordal initialization [1,2] to arbitrary matrix Lie groups, and additionally proposes two new key algorithmic enhancements: we show how to exploit both the Kronecker-product structure in the problem data matrix and the topology of the synchronization graph to improve speed, scalability, and accuracy. Experimental evaluation across several GS tasks demonstrates that <italic>Fast-Sync</italic> provides high-quality initializations that enable local optimizers to efficiently recover globally optimal GS solutions, achieving high success rates even with considerable measurement noise.