Error bounds for discretized optimal transport and its reliable efficient numerical solution
For researchers in optimal transport, this work provides theoretical guarantees and an efficient algorithm for solving large-scale discretized problems.
The paper derives error estimates for discretized optimal transport and proposes an active-set multilevel strategy that achieves linear growth of effective problem size with respect to discretization variables, confirmed by numerical experiments.
The discretization of optimal transport problems often leads to large linear programs with sparse solutions. We derive error estimates for the approximation of the problem using convex combinations of Dirac measures and devise an active-set strategy that uses the optimality conditions to predict the support of a solution within a multilevel strategy. Numerical experiments confirm the theoretically predicted convergence rates and a linear growth of effective problem sizes with respect to the variables used to discretize given data.