# Synchronisation of Partial Multi-Matchings via Non-negative Factorisations

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2018.

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

- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [SRIF: Semantic Shape Registration Empowered by Diffusion-based Image Morphing and Flow Estimation](https://mlsanity.com/paper/2409.11682/) (2024)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)
- [Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching](https://mlsanity.com/paper/2201.04797/) (2022)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Non-Rigid 3D Shape Correspondences: From Foundations to Open Challenges and Opportunities](https://mlsanity.com/paper/2604.01274/) (2026)
- [Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections](https://mlsanity.com/paper/2103.17229/) (2021)
- [Universe Points Representation Learning for Partial Multi-Graph Matching](https://mlsanity.com/paper/2212.00780/) (2022)
- [Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimaging](https://mlsanity.com/paper/2406.18215/) (2024)
- [MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities](https://mlsanity.com/paper/2210.08360/) (2022)
- [Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering](https://mlsanity.com/paper/2310.13311/) (2023)
- [DcMatch: Unsupervised Multi-Shape Matching with Dual-Level Consistency](https://mlsanity.com/paper/2509.01204/) (2025)
- [Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis](https://mlsanity.com/paper/2112.04165/) (2021)
- [Leveraging Cycle-Consistent Anchor Points for Self-Supervised RGB-D Registration](https://mlsanity.com/paper/2510.14354/) (2025)
- [Recovery Theory for Projected Power Iterations in Permutation Synchronization](https://mlsanity.com/paper/2609.09502/) (2026)

## Abstract (arXiv)

In this work we study permutation synchronisation for the challenging case of partial permutations, which plays an important role for the problem of matching multiple objects (e.g. images or shapes). The term synchronisation refers to the property that the set of pairwise matchings is cycle-consistent, i.e. in the full matching case all compositions of pairwise matchings over cycles must be equal to the identity. Motivated by clustering and matrix factorisation perspectives of cycle-consistency, we derive an algorithm to tackle the permutation synchronisation problem based on non-negative factorisations. In order to deal with the inherent non-convexity of the permutation synchronisation problem, we use an initialisation procedure based on a novel rotation scheme applied to the solution of the spectral relaxation. Moreover, this rotation scheme facilitates a convenient Euclidean projection to obtain a binary solution after solving our relaxed problem. In contrast to state-of-the-art methods, our approach is guaranteed to produce cycle-consistent results. We experimentally demonstrate the efficacy of our method and show that it achieves better results compared to existing methods.