On the curse of dimension in multi-marginal optimal transport and its numerical methods

  • Maximilian Penka (TU München)
E2 10 (Leon-Lichtenstein)


In recent times, mathematicians have increasingly formulated problems related to strongly interacting systems as multi-marginal optimal transport (MMOT) problems. From a theoretical point of view, this formulation is helpful because a MMOT problem is convex, and one can use a well-developed and strong duality theory.

Unfortunately, the problem suffers extremely from the curse of dimension in that one seeks a solution in the product space of the marginal spaces, making direct application of algorithms from regular OT theory difficult.

Therefore, [FSV22] introduced a genetic modification of the column generation algorithm to solve an MMOT problem from DFT. This algorithm, respectively its extension to general MMOT problems, reduces the data complexity from $O(\ell^N)$ to $O(N*\ell)$ ($N$ the number and $\ell$ the cardinality of the marginals). It can also be shown that in the classical case of N=2 marginals, the algorithm always converges to the global optimum and reduces the data complexity, which may also make it interesting for large classical OT problems.

Friesecke, Schulz, Vögler (2022). Genetic column generation: Fast computation of high-dimensional multimarginal optimal transport problems. SIAM Journal on Scientific Computing, 44(3), A1632-A1654.

Katja Heid

MPI for Mathematics in the Sciences Contact via Mail

Upcoming Events of This Seminar

  • 30.04.2024 tba with Annika Burmester
  • 07.05.2024 tba with Christian Wagner
  • 21.05.2024 tba with Immanuel Zachhuber
  • 21.05.2024 tba with Da Li
  • 31.05.2024 tba with Olga Shishkina
  • 06.06.2024 tba with Christiane Klein