# Near-Optimal Joint Object Matching via Convex Relaxation

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2014.

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

- [Scene Synthesis via Uncertainty-Driven Attribute Synchronization](https://mlsanity.com/paper/2108.13499/) (2021)
- [Quantum Motion Segmentation](https://mlsanity.com/paper/2203.13185/) (2022)
- [GenCorres: Consistent Shape Matching via Coupled Implicit-Explicit Shape Generative Models](https://mlsanity.com/paper/2304.10523/) (2023)
- [Robust Group Synchronization via Quadratic Programming](https://mlsanity.com/paper/2206.08994/) (2022)
- [A Survey on Computational Solutions for Reconstructing Complete Objects by Reassembling Their Fractured Parts](https://mlsanity.com/paper/2410.14770/) (2024)
- [Fast, Accurate and Memory-Efficient Partial Permutation Synchronization](https://mlsanity.com/paper/2203.16505/) (2022)
- [Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching](https://mlsanity.com/paper/2201.04797/) (2022)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (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)
- [Population-wise Labeling of Sulcal Graphs using Multi-graph Matching](https://mlsanity.com/paper/2301.13532/) (2023)
- [A Novel and Optimal Spectral Method for Permutation Synchronization](https://mlsanity.com/paper/2303.12051/) (2023)
- [Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering](https://mlsanity.com/paper/2310.13311/) (2023)
- [AlignGraph: A Group of Generative Models for Graphs](https://mlsanity.com/paper/2301.11273/) (2023)
- [M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering](https://mlsanity.com/paper/2310.18444/) (2023)
- [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)

Joint matching over a collection of objects aims at aggregating information from a large collection of similar instances (e.g. images, graphs, shapes) to improve maps between pairs of them. Given multiple matches computed between a few object pairs in isolation, the goal is to recover an entire collection of maps that are (1) globally consistent, and (2) close to the provided maps --- and under certain conditions provably the ground-truth maps. Despite recent advances on this problem, the best-known recovery guarantees are limited to a small constant barrier --- none of the existing methods find theoretical support when more than 50% of input correspondences are corrupted. Moreover, prior approaches focus mostly on fully similar objects, while it is practically more demanding to match instances that are only partially similar to each other. In this paper, we develop an algorithm to jointly match multiple objects that exhibit only partial similarities, given a few pairwise matches that are densely corrupted. Specifically, we propose to recover the ground-truth maps via a parameter-free convex program called MatchLift, following a spectral method that pre-estimates the total number of distinct elements to be matched. Encouragingly, MatchLift exhibits near-optimal error-correction ability, i.e. in the asymptotic regime it is guaranteed to work even when a dominant fraction 1-Thetaleft(fraclog2n√nright) of the input maps behave like random outliers. Furthermore, MatchLift succeeds with minimal input complexity, namely, perfect matching can be achieved as soon as the provided maps form a connected map graph. We evaluate the proposed algorithm on various benchmark data sets including synthetic examples and real-world examples, all of which confirm the practical applicability of MatchLift.