Message-passing algorithms for synchronization problems over compact groups
Amelia Perry Note: The first two authors contributed equally. Thanks: Email: This work is supported in part by NSF CAREER Award CCF-1453261 and a grant from the MIT NEC Corporation. Affiliation: Department of Mathematics, Massachusetts Institute of Technology Alexander S. Wein Thanks: Email: This research was conducted with Government support under and awarded by DoD, Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. Affiliation: Department of Mathematics, Massachusetts Institute of Technology Afonso S. Bandeira Thanks: Email: A.S.B. was supported by NSF Grant DMS-1317308. Part of this work was done while A.S.B. was with the Department of Mathematics at the Massachusetts Institute of Technology. Affiliation: Department of Mathematics and Center for Data Science, Courant Institute of Mathematical Sciences, New York University, NY, USA Ankur Moitra Thanks: Email: This work is supported in part by NSF CAREER Award CCF-1453261, a grant from the MIT NEC Corporation and a Google Faculty Research Award. Affiliation: Department of Mathematics, Massachusetts Institute of Technology Affiliation: Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology
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 $\mathbb{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, (
原文 arXiv:1610.04583;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1610.04583v1