Abstract for the talk on 02.06.2023 (11:00 h)AG Analysis-Probability
Maximilian Penka (TU München)
On the curse of dimension in multi-marginal optimal transport and its numerical methods
02.06.2023, 11:00 h, MPI für Mathematik in den Naturwissenschaften Leipzig, 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(^N) to O(N*) (N the number and 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.