BIRS Workshop Lecture Videos
Approximation of OT problems with marginal moments constraints Coyaud, Rafael
We introduce a relaxation of the OT problem (Moments Constrained Optimal Transport, MCOT) by minimizing the OT cost over the set of measures having only N moments against some given test functions equal to the ones of each marginal law. Using Tchakaloffâ s theorem, we show that a finite discrete measure minimizes this problem which charges at most DN+2 points, with D the number of marginal laws. In addition, we prove the convergence of the MCOT problems towards the OT problem as the number of moments imposed goes to infinity, under some appropriate assumptions on the set of test functions. In this context, the convergence rate with respect to the number of moment constraints depends on the choice of test functions and cost considered. We present quantitative estimates for this rate in the particular cases of piecewise constant and affine test functions. Although the resulting MCOT problem is non convex, the linear dependency of the number of charged points of an optimum in the number of marginal laws and test functions is of algorithmic interest for the resolution of multi-marginal optimal transport problems with a very large number of marginal laws. This situation is typically encountered in the context of DFT. We thus propose two algorithms for the resolution of the MCOT problem which exploits this particular structure.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International