Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
Preprint
Abstract
Replacing positivity constraints by an entropy barrier is popular to approximate solutions of linear programs. In the special case of the optimal transport problem, this technique dates back to the early work of Schr\"odinger. This approach has recently been used successfully to solve optimal transport related problems in several applied fields such as imaging sciences, machine learning and social sciences. The main reason for this success is that, in contrast to linear programming solvers, the resulting algorithms are highly parallelizable and take advantage of the geometry of the computational grid (e.g. an image or a triangulated mesh). The first contribution of this article is the proof of the $\Gamma$-convergence of the entropic regularized optimal transport problem towards the Monge-Kantorovich problem for the squared Euclidean norm cost function. This implies in particular the convergence of the optimal entropic regularized transport plan towards an optimal transport plan as the entropy vanishes. Optimal transport distances are also useful to define gradient flows as a limit of implicit Euler steps according to the transportation distance. Our second contribution is a proof that implicit steps according to the entropic regularized distance converge towards the original gradient flow when both the step size and the entropic penalty vanish (in some controlled way).Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equationESAIM: Mathematical Modelling and Numerical Analysis, 2014
- Monge–Ampére based moving mesh methods for numerical weather prediction, with applications to the Eady problemJournal of Computational Physics, 2013
- One-Dimensional Numerical Algorithms for Gradient Flows in the p-Wasserstein SpacesActa Applicandae Mathematicae, 2012
- From a Large-Deviations Principle to the Wasserstein Gradient Flow: A New Micro-Macro PassageCommunications in Mathematical Physics, 2011
- Variational particle schemes for the porous medium equation and for the system of isentropic Euler equationsESAIM: Mathematical Modelling and Numerical Analysis, 2009
- The Wasserstein Gradient Flow of the Fisher Information and the Quantum Drift-diffusion EquationArchive for Rational Mechanics and Analysis, 2008
- THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATIONCommunications in Partial Differential Equations, 2001
- Dykstras algorithm with bregman projections: A convergence proofOptimization, 2000
- Approximation of Parabolic Equations Using the Wasserstein MetricESAIM: Mathematical Modelling and Numerical Analysis, 1999
- Asymptotic analysis of the exponential penalty trajectory in linear programmingMathematical Programming, 1994