# Higher-order Projected Power Iterations for Scalable Multi-Matching

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2018.

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

- [Unsupervised Learning of Robust Spectral Shape Matching](https://mlsanity.com/paper/2304.14419/) (2023)
- [Unsupervised Deep Multi-Shape Matching](https://mlsanity.com/paper/2207.09610/) (2022)
- [C2M3: Cycle-Consistent Multi-Model Merging](https://mlsanity.com/paper/2405.17897/) (2024)
- [A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2204.12805/) (2022)
- [Quantum Motion Segmentation](https://mlsanity.com/paper/2203.13185/) (2022)
- [CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes](https://mlsanity.com/paper/2303.16202/) (2023)
- [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)
- [TsCA: On the Semantic Consistency Alignment via Conditional Transport for Compositional Zero-Shot Learning](https://mlsanity.com/paper/2408.08703/) (2024)
- [ExGra-Med: Extended Context Graph Alignment for Medical Vision-Language Models](https://mlsanity.com/paper/2410.02615/) (2024)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections](https://mlsanity.com/paper/2103.17229/) (2021)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [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)
- [Test-Time Domain Generalization via Universe Learning: A Multi-Graph Matching Approach for Medical Image Segmentation](https://mlsanity.com/paper/2503.13012/) (2025)
- [Population-wise Labeling of Sulcal Graphs using Multi-graph Matching](https://mlsanity.com/paper/2301.13532/) (2023)
- [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)
- [Hyper-Network Neural Functional Maps for Unsupervised Robust 3D Shape Matching](https://mlsanity.com/paper/2606.30131/) (2026)
- [Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis](https://mlsanity.com/paper/2112.04165/) (2021)
- [Prior-free relative 6D pose estimation of multiple object instances](https://mlsanity.com/paper/2609.08949/) (2026)
- [Recovery Theory for Projected Power Iterations in Permutation Synchronization](https://mlsanity.com/paper/2609.09502/) (2026)

## Abstract (arXiv)

The matching of multiple objects (e.g. shapes or images) is a fundamental problem in vision and graphics. In order to robustly handle ambiguities, noise and repetitive patterns in challenging real-world settings, it is essential to take geometric consistency between points into account. Computationally, the multi-matching problem is difficult. It can be phrased as simultaneously solving multiple (NP-hard) quadratic assignment problems (QAPs) that are coupled via cycle-consistency constraints. The main limitations of existing multi-matching methods are that they either ignore geometric consistency and thus have limited robustness, or they are restricted to small-scale problems due to their (relatively) high computational cost. We address these shortcomings by introducing a Higher-order Projected Power Iteration method, which is (i) efficient and scales to tens of thousands of points, (ii) straightforward to implement, (iii) able to incorporate geometric consistency, (iv) guarantees cycle-consistent multi-matchings, and (iv) comes with theoretical convergence guarantees. Experimentally we show that our approach is superior to existing methods.