Session III.3 - Computational Optimal Transport
Poster
Genetic Column Generation: Convergence proof and application to transport splines on the Wasserstein space
Maximilian Penka
Technische Universität München, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Solving multi-marginal optimal transport problems numerically is a challenging task as it suffers from the curse of dimension. The curse occurs not only in computing time, but already in data complexity. For $N$ marginals, each of them discretized on $\ell$ support points, the corresponding linear program has $\ell^N$ unknowns. On the other hand, the problem is known to have an extremal solution with support size at most $N(\ell - 1) + 1$, equal to the number of independent constraints. This gave rise to a new algorithm that updates the set of admissible support points genetically while maintaining its guaranteed sparsity.
On my poster, I will briefly explain the algorithm, provide a proof of convergence for the classical $N = 2$ marginal case, and demonstrate a numerical application for second-order interpolations on the Wasserstein space.
Joint work with Gero Friesecke (Technische Universität München, Germany).