arXiv preprint ·
A Unified Dual Method for Matching Problems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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..
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
A differentiability framework for zigzag persistent homology via linear interpolation
Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance
Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model
Fair Diversity Maximization via Local Search
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.