Message-passing algorithms for synchronization problems over compact groups
Amelia Perry111The first two authors contributed equally. Email: This work is supported in part by NSF CAREER Award CCF-1453261 and a grant from the MIT NEC Corporation. Department of Mathematics, Massachusetts Institute of Technology Alexander S. Wein 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. Department of Mathematics, Massachusetts Institute of Technology Afonso S. Bandeira 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. Department of Mathematics and Center for Data Science, Courant Institute of Mathematical Sciences, New York University, NY, USA Ankur Moitra 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. Department of Mathematics, Massachusetts Institute of Technology 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, (
中文速览
冷冻电镜、社群侦测、时间同步等领域里都存在一类"同步问题"（synchronization problem）：已知一组带噪声的群元素之间的相对观测值，要还原出每个未知的群元素。现有方法要么用主成分分析（PCA）忽略了群结构，要么用投影幂迭代却在低信噪比时失效，而且都难以同时利用多个频率通道的信息。本文提出一种基于近似消息传递（approximate message passing，AMP）框架的高效迭代算法，将表示论（representation theory）融入AMP的推导，使其能处理任意紧群、任意多个不可约表示通道的同步问题。通过统计物理的空腔方法对算法进行理论分析，推导出精确描述算法行为的"状态演化"方程，结果表明：算法的相变阈值与PCA相同（信噪比超过1即可获得非平凡估计），但阈值以上的估计误差显著优于PCA和投影幂迭代，且在多频道实验中估计误差可降低数个数量级；在许多参数区间内，该算法在信息论意义上是最优的，其余区间则呈现出统计可行与计算可行之间的"鸿沟"。这一工作为冷冻电镜等实际应用提供了理论上有保障、实践上高效的群同步求解方案。
原文 arXiv:1610.04583;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1610.04583v1