# Fast, Accurate and Memory-Efficient Partial Permutation Synchronization

arXiv: https://arxiv.org/abs/2203.16505 · HTML: https://mlsanity.com/paper/2203.16505/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 30 references that are in the map.
- First posted on arXiv 30 Mar 2022.

## Builds on (most cited first, 11 of 11)

- [Robust Camera Location Estimation by Convex Programming](https://mlsanity.com/paper/1412.0165/) (2014)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [Message Passing Least Squares Framework and its Application to Rotation Synchronization](https://mlsanity.com/paper/2007.13638/) (2020)
- [Robust Group Synchronization via Cycle-Edge Message Passing](https://mlsanity.com/paper/1912.11347/) (2019)
- [Near-Optimal Joint Object Matching via Convex Relaxation](https://mlsanity.com/paper/1402.1473/) (2014)
- [The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences](https://mlsanity.com/paper/1609.05820/) (2016)
- [Multi-Image Semantic Matching by Mining Consistent Features](https://mlsanity.com/paper/1711.07641/) (2017)
- [A New Rank Constraint on Multi-view Fundamental Matrices, and its Application to Camera Location Recovery](https://mlsanity.com/paper/1702.03023/) (2017)
- [Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian](https://mlsanity.com/paper/2006.06658/) (2020)
- [Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching](https://mlsanity.com/paper/2201.04797/) (2022)

## Built on by (most cited first, 8 of 8)

- [A Survey on Computational Solutions for Reconstructing Complete Objects by Reassembling Their Fractured Parts](https://mlsanity.com/paper/2410.14770/) (2024)
- [Pooling Image Datasets With Multiple Covariate Shift and Imbalance](https://mlsanity.com/paper/2403.02598/) (2024)
- [Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization](https://mlsanity.com/paper/2407.04260/) (2024)
- [Tensor-Based Synchronization and the Low-Rankness of the Block Trifocal Tensor](https://mlsanity.com/paper/2409.09313/) (2024)
- [Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization](https://mlsanity.com/paper/2511.02329/) (2025)
- [MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities](https://mlsanity.com/paper/2210.08360/) (2022)
- [C-DOG: Multi-View Multi-instance Feature Association Using Connected δ-Overlap Graphs](https://mlsanity.com/paper/2507.14095/) (2025)
- [Recovery Theory for Projected Power Iterations in Permutation Synchronization](https://mlsanity.com/paper/2609.09502/) (2026)

## Abstract (arXiv)

Previous partial permutation synchronization (PPS) algorithms, which are commonly used for multi-object matching, often involve computation-intensive and memory-demanding matrix operations. These operations become intractable for large scale structure-from-motion datasets. For pure permutation synchronization, the recent Cycle-Edge Message Passing (CEMP) framework suggests a memory-efficient and fast solution. Here we overcome the restriction of CEMP to compact groups and propose an improved algorithm, CEMP-Partial, for estimating the corruption levels of the observed partial permutations. It allows us to subsequently implement a nonconvex weighted projected power method without the need of spectral initialization. The resulting new PPS algorithm, MatchFAME (Fast, Accurate and Memory-Efficient Matching), only involves sparse matrix operations, and thus enjoys lower time and space complexities in comparison to previous PPS algorithms. We prove that under adversarial corruption, though without additive noise and with certain assumptions, CEMP-Partial is able to exactly classify corrupted and clean partial permutations. We demonstrate the state-of-the-art accuracy, speed and memory efficiency of our method on both synthetic and real datasets.