In synchronization tasks, a collection of entities have latent 'alignments' drawn from some symmetry group, and the task is to recover the relative alignments based on very noisy pairwise observations. A central example is the recovery of molecule rotations in cryo-electron microscopy. We present a new algorithm following the framework of approximate message passing, which statistical physics suggests may yield the optimal reconstruction. Our approach leverages the representation theory of compact groups to give a unified approach for all such problems. The algorithm is efficient, resembling power iteration for PCA -- but after each matrix-vector product, we add an Onsager correction term originating in statistical physics, and then perform a nonlinear transformation that combines data from different 'frequency channels' -- that is, from different irreducible representations of the group. By contrast, many previous algorithms use only one Fourier component of the observations (a notable exception being the Non-Unique Games semidefinite programming approach). The algorithm has a natural derivation from belief propagation, and an interpretation that alternates between belief distributions and an additive 'confidence' representation. We will present empirical results of its strength over many groups and noise models, and discuss theoretical questions and results about the quality of its recovery.
Joint work with Amelia Perry, Afonso Bandeira, and Ankur Moitra.