We propose a general framework for solving the group synchronization problem, where we focus on the setting of adversarial or uniform corruption and sufficiently small noise. Specifically, we apply a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of group ratios and consequently solve the synchronization problem in our setting. We first explain why the group cycle consistency information is essential for effectively solving group synchronization problems. We then establish exact recovery and linear convergence guarantees for the proposed message passing procedure under a deterministic setting with adversarial corruption. These guarantees hold as long as the ratio of corrupted cycles per edge is bounded by a reasonable constant. We also establish the stability of the proposed procedure to sub-Gaussian noise. We further establish exact recovery with high probability under a common uniform corruption model.
翻译:我们提出了一个解决群体同步问题的总体框架,我们在此集中关注对抗性或统一腐败的设置和足够小的噪音。具体地说,我们采用一种新的信息传递程序,使用周期一致性信息来估计群体比率的腐败程度,从而解决我们所处的同步问题。我们首先解释为什么群体周期一致性信息对于有效解决群体同步问题至关重要。然后,我们在对抗性腐败的决定性背景下,为拟议的信息传递程序确立准确的回收和线性趋同保证。这些保证只要每个边缘的腐败循环比率受合理的常数约束,就维持不变。我们还将拟议程序稳定到亚高加索噪音。我们还在共同的统一腐败模式下,非常有可能地确定准确的回收。