Georgia Institute of Technology College of Sciences

The problem of partial permutation synchronization (PPS) provides a global mathematical formulation for the multiple image matching problem. In this matching problem, one is provided with possibly corrupted matches (i.e., partial permutations) between keypoints in pairs of images and the underlying task is to match keypoints in each image to universal 3D scene points (resulting in other partial permutations). For structure-from-motion (SfM) common datasets, previous PPS algorithms for image matching often become computationally intractable and demand an exceedingly large amount of memory. We address this issue by extending the recent framework of Cycle-Edge Message Passing (CEMP) to the setting of PPS despite the fact that partial permutations do not have a full group structure.  We emphasize mathematical difficulties that arise when extending CEMP to PPS and also explain the mathematical guarantees for the performance of the modified CEMP algorithm in the setting of adversarial corruption and sufficiently small noise. This is a joint work with Shaohan Li and Yunpeng Shi.