Collision-based Dynamics for Multi-Marginal Optimal Transport
This addresses computational bottlenecks in optimal transport for high-dimensional applications like machine learning and physics.
The paper tackles the computational challenge of solving multi-marginal optimal transport problems by proposing a collision-based dynamics method with Monte Carlo sampling, achieving linear scaling in complexity and memory usage with sample size and demonstrating efficiency compared to state-of-the-art methods.
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.