The Taub Faculty of Computer Science Events and Talks

The general synchronization problem asks to recover states of objects from their corrupted relative measurements. When the states are represented by group elements (e.g. 3-D rotations or permutations) this problem is known as group synchronization. In several applications, the algebraic structure of the states is more complicated, for example, the states can be represented by partial permutations. The synchronization problem has many applications, in particular, to structure-from-motion (SfM), where one needs to estimate the 3D structure of a scene from a set of its projected 2D images. I will first describe a general framework for group synchronization, the Cycle-Edge Message Passing (CEMP), and then explain its generalization to non-groups, by exemplifying the case of partial permutation synchronization. I will emphasize mathematical difficulties, review some mathematical guarantees for the proposed methods and also demonstrate an application. This is a joint work with Shaohan Li and Yunpeng Shi.