# Initialization and Coordinate Optimization for Multi-way Matching

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

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

- [Unsupervised Deep Graph Matching Based on Cycle Consistency](https://mlsanity.com/paper/2307.08930/) (2023)
- [Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimaging](https://mlsanity.com/paper/2406.18215/) (2024)
- [Recovery Theory for Projected Power Iterations in Permutation Synchronization](https://mlsanity.com/paper/2609.09502/) (2026)

## Abstract (arXiv)

We consider the problem of consistently matching multiple sets of elements to each other, which is a common task in fields such as computer vision. To solve the underlying NP-hard objective, existing methods often relax or approximate it, but end up with unsatisfying empirical performance due to a misaligned objective. We propose a coordinate update algorithm that directly optimizes the target objective. By using pairwise alignment information to build an undirected graph and initializing the permutation matrices along the edges of its Maximum Spanning Tree, our algorithm successfully avoids bad local optima. Theoretically, with high probability our algorithm guarantees an optimal solution under reasonable noise assumptions. Empirically, our algorithm consistently and significantly outperforms existing methods on several benchmark tasks on real datasets.