View abstract

Session III.3 - Computational Optimal Transport


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).

View abstract PDF