Robust Group Synchronization via Cycle-Edge Message Passing

DOI10.1007/S10208-021-09532-WMaRDI QIDQ6331754arXivFDO

Authors Gilad Lerman, Yunpeng Shi

Publication date 24 December 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10208-021-09532-W

Mathematics Subject Classification ID

Nonparametric robustness (62G35) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Analysis of algorithms (68W40) Estimation and detection in stochastic control theory (93E10)

arXiv classification

cs.ITmath.ITmath.OCmath.PRstat.ML

Abstract: 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.

This page was built for publication: Robust Group Synchronization via Cycle-Edge Message Passing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6331754)