TY - JOUR

T1 - Message-Passing Algorithms for Synchronization Problems over Compact Groups

AU - Perry, Amelia

AU - Wein, Alexander S.

AU - Bandeira, Afonso S.

AU - Moitra, Ankur

N1 - Funding Information:
A.P.: This work is supported in part by National Science Foundation Grant DMS-1541100, NSF CAREER Award CCF-1453261, and a grant from the MIT NEC Corporation.
Funding Information:
A.S.W.: This research was conducted with government support awarded by and under the Department of Defense, Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a.
Funding Information:
A.S.B.: This work was partially supported by National Science Foundation Grants DMS-1317308, DMS-1712730, and DMS-1719545. Part of this work was done while A.S.B. was with the Department of Mathematics at the Massachusetts Institute of Technology.
Funding Information:
A.M.: This work is supported in part by National Science Foundation CAREER Award CCF-1453261, a grant from the MIT NEC Corporation, and a Google Faculty Research Award.

PY - 2018/11

Y1 - 2018/11

N2 - 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 ℤ/L, U(1), or SO(3). The goal in 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 general compact groups. Using standard but nonrigorous methods from statistical physics, we analyze the behavior of our algorithm on a Gaussian noise model, identifying phases where we believe 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 exhibit statistical-to-computational gaps.

AB - 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 ℤ/L, U(1), or SO(3). The goal in 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 general compact groups. Using standard but nonrigorous methods from statistical physics, we analyze the behavior of our algorithm on a Gaussian noise model, identifying phases where we believe 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 exhibit statistical-to-computational gaps.

UR - http://www.scopus.com/inward/record.url?scp=85044783392&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044783392&partnerID=8YFLogxK

U2 - 10.1002/cpa.21750

DO - 10.1002/cpa.21750

M3 - Article

AN - SCOPUS:85044783392

VL - 71

SP - 2275

EP - 2322

JO - Communications on Pure and Applied Mathematics

JF - Communications on Pure and Applied Mathematics

SN - 0010-3640

IS - 11

ER -