# Collision-based Dynamics for Multi-Marginal Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 20 Dec 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Manifold Interpolating Optimal-Transport Flows for Trajectory Inference](https://mlsanity.com/paper/2206.14928/) (2022)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [On the representation and learning of monotone triangular transport maps](https://mlsanity.com/paper/2009.10303/) (2020)
- [Fine-Grained Representation Learning and Recognition by Exploiting Hierarchical Semantic Embedding](https://mlsanity.com/paper/1808.04505/) (2018)
- [A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance](https://mlsanity.com/paper/2012.05199/) (2020)
- [Projected Langevin dynamics and a gradient flow for entropic optimal transport](https://mlsanity.com/paper/2309.08598/) (2023)
- [Multi-marginal optimal transport and probabilistic graphical models](https://mlsanity.com/paper/2006.14113/) (2020)
- [Robust clustering tools based on optimal transportation](https://mlsanity.com/paper/1607.01179/) (2016)
- [Moment-SoS Methods for Optimal Transport Problems](https://mlsanity.com/paper/2211.10742/) (2022)
- [Optimal Transportation by Orthogonal Coupling Dynamics](https://mlsanity.com/paper/2410.08060/) (2024)

## Abstract (arXiv)

Inspired by the Boltzmann kinetics, we propose a collision-based dynamics with a Monte Carlo solution algorithm that approximates the solution of the multi-marginal optimal transport problem via randomized pairwise swapping of sample indices. The computational complexity and memory usage of the proposed method scale linearly with the number of samples, making it highly attractive for high-dimensional settings. In several examples, we demonstrate the efficiency of the proposed method compared to the state-of-the-art methods.