IDeAS Seminar: Yunpeng Shi, University of Minnesota

Wed, Feb 5, 2020, 1:30 pm

Robust Group Synchronization via Cycle-Edge Message Passing

We propose a general framework for group synchronization with adversarial 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 infers the corrupted group ratios and solves the synchronization problem. 

We establish exact recovery and linear convergence guarantees for the proposed algorithm 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 show that under a uniform corruption model, the recovery results are sharp in terms of an information-theoretic bound.

Yunpeng Shi is a Ph.D. candidate in the school of mathematics at the University of Minnesota, under the supervision of Prof. Gilad Lerman. He obtained his bachelor's degree from the University of Minnesota. He has been working on structure from motion (SfM) and its associated inverse problems. His current work is on robust group synchronization that has applications in 3D reconstruction, cryo-electron microscopy imaging, multi-graph matching, and community detection.

224 Fine Hall
Event category: 

Upcoming Events

Prof. Afonso Bandeira, ETH Zurich

Mon, Sep 11, 2023, 4:30 pm
Location: 214 Fine Hall

Prof. Jonathan Pillow, Princeton University

Mon, Sep 18, 2023, 4:30 pm
Location: 214 Fine Hall

No PACM Colloquium scheduled on this day-Yom Kippur

Mon, Sep 25, 2023, 4:30 pm
Location: 214 Fine Hall