# A Unified Dual Method for Matching Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 30 Sep 2026.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Word Translation Without Parallel Data](https://mlsanity.com/paper/1710.04087/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Towards Optimal Transport with Global Invariances](https://mlsanity.com/paper/1806.09277/) (2018)
- [GARF: Learning Generalizable 3D Reassembly for Real-World Fractures](https://mlsanity.com/paper/2504.05400/) (2025)
- [FlashSinkhorn: IO-Aware Entropic Optimal Transport on GPU](https://mlsanity.com/paper/2602.03067/) (2026)
- [Structured Transforms Across Spaces with Cost-Regularized Optimal Transport](https://mlsanity.com/paper/2311.05788/) (2023)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Gromov-Wasserstein at Scale, Beyond Squared Norms](https://mlsanity.com/paper/2602.06658/) (2026)
- [Quadratic-form Optimal Transport](https://mlsanity.com/paper/2501.04658/) (2025)
- [Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods](https://mlsanity.com/paper/2602.10697/) (2026)

## Abstract (arXiv)

Matching problems are ubiquitous in data science as they enable the alignment of structured objects and distributions. While existing solvers are often tailored to specific matching formulations, we unify a broad class of such problems within a common mathematical and optimization framework based on duality theory. Theoretically, we demonstrate that matching objectives decomposable as a difference of convex (DC) functions can be recast as implicit registration problems. This connection links matching to another well-studied class of objectives and yields a dual formulation amenable to natural optimization strategies. We then apply these findings to quadratic matching (QM) problems, which admit DC decompositions and for which we provide extensive convergence guarantees. Our framework applies to Gromov-Wasserstein (GW), as well as its unbalanced formulation and several variants, which are increasingly popular QM problems. Numerically, we implement our algorithms at scale for various data modalities such as graphs, point clouds, meshes, and word embeddings. Finally, our modular approach allows us to explore new formulations such as fracture matching, broadening the scope of problems that can be addressed within this framework..