Message-passing algorithms for synchronization problems over compact groups

Abstract

Various alignment problems arising in cryo-electron microscopy, community detection, time synchronization, computer vision, and other fields fall into a common framework of synchronization problems over compact groups such as Z/L, U(1), or SO(3). The goal of such problems is to estimate an unknown vector of group elements given noisy relative observations. We present an efficient iterative algorithm to solve a large class of these problems, allowing for any compact group, with measurements on multiple 'frequency channels' (Fourier modes, or more generally, irreducible representations of the group). Our algorithm is a highly efficient iterative method following the blueprint of approximate message passing (AMP), which has recently arisen as a central technique for inference problems such as structured low-rank estimation and compressed sensing. We augment the standard ideas of AMP with ideas from representation theory so that the algorithm can work with distributions over compact groups. Using standard but non-rigorous methods from statistical physics we analyze the behavior of our algorithm on a Gaussian noise model, identifying phases where the problem is easy, (computationally) hard, and (statistically) impossible. In particular, such evidence predicts that our algorithm is information-theoretically optimal in many cases, and that the remaining cases show evidence of statistical-to-computational gaps.

35 pages, 11 figures

References in corpus (5)

• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Mutual Information in Rank-One Matrix Estimation
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Community detection with nodal information

Cited by in corpus (21)

• Bispectrum Inversion with Application to Multireference Alignment
• Estimation under group actions: recovering orbits from invariants
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• The generalized method of moments for multi-reference alignment
• PCA Initialization for Approximate Message Passing in Rotationally Invariant Models
• An accelerated expectation-maximization algorithm for multi-reference alignment
• Message Passing Least Squares Framework and its Application to Rotation Synchronization
• Robust Group Synchronization via Cycle-Edge Message Passing
• Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian
• Quartic quantum speedups for planted inference
• Representation Theoretic Patterns in Multi-Frequency Class Averaging for Three-Dimensional Cryo-Electron Microscopy
• Tightness of the semidefinite relaxation for orthogonal trace-sum maximization
• Multi-Frequency Joint Community Detection and Phase Synchronization
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• The planted XY model: thermodynamics and inference
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Template Matching and Change Point Detection by M-estimation
• Shotgun identification on groups
• Multi-Frequency Phase Synchronization