Computation of optimal transport on discrete metric measure spaces

被引:0
作者
Matthias Erbar
Martin Rumpf
Bernhard Schmitzer
Stefan Simon
机构
[1] University of Bonn,Institute for Applied Mathematics
[2] University of Bonn,Institute for Numerical Simulation
[3] Technical University of Munich,Department of Mathematics
来源
Numerische Mathematik | 2020年 / 144卷
关键词
Optimal transport on graphs; Proximal splitting; Gradient flows; 65K10; 49M29; 49Q20; 60J27;
D O I
暂无
中图分类号
学科分类号
摘要
In this paper we investigate the numerical approximation of an analogue of the Wasserstein distance for optimal transport on graphs that is defined via a discrete modification of the Benamou–Brenier formula. This approach involves the logarithmic mean of measure densities on adjacent nodes of the graph. For this model a variational time discretization of the probability densities on graph nodes and the momenta on graph edges is proposed. A robust descent algorithm for the action functional is derived, which in particular uses a proximal splitting with an edgewise nonlinear projection on the convex subgraph of the logarithmic mean. Thereby, suitable chosen slack variables avoid a global coupling of probability densities on all graph nodes in the projection step. For the time discrete action functional Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document}-convergence to the time continuous action is established. Numerical results for a selection of test cases show qualitative and quantitative properties of the optimal transport on graphs. Finally, we use our algorithm to implement a JKO scheme for the gradient flow of the entropy in discrete transportation distance, which is known to coincide with underlying Markov semigroup, and test our results against a classical backward Euler discretization of this discrete heat flow.
引用
收藏
页码:157 / 200
页数:43
相关论文
共 37 条
  • [1] Computation of optimal transport on discrete metric measure spaces
    Erbar, Matthias
    Rumpf, Martin
    Schmitzer, Bernhard
    Simon, Stefan
    NUMERISCHE MATHEMATIK, 2020, 144 (01) : 157 - 200
  • [2] Regularized Discrete Optimal Transport
    Ferradans, Sira
    Papadakis, Nicolas
    Peyre, Gabriel
    Aujol, Jean-Francois
    SIAM JOURNAL ON IMAGING SCIENCES, 2014, 7 (03): : 1853 - 1882
  • [3] On the p-Laplacian evolution equation in metric measure spaces
    Corny, Wojciech
    Mazon, Jose M.
    JOURNAL OF FUNCTIONAL ANALYSIS, 2022, 283 (08)
  • [4] The Neumann and Dirichlet problems for the total variation flow in metric measure spaces
    Gorny, Wojciech
    Mazon, Jose M.
    ADVANCES IN CALCULUS OF VARIATIONS, 2024, 17 (01) : 131 - 164
  • [5] METRIC MEASURE SPACES WITH RIEMANNIAN RICCI CURVATURE BOUNDED FROM BELOW
    Ambrosio, Luigi
    Gigli, Nicola
    Savare, Giuseppe
    DUKE MATHEMATICAL JOURNAL, 2014, 163 (07) : 1405 - 1490
  • [6] A discrete Schrodinger equation via optimal transport on graphs
    Chow, Shui-Nee
    Li, Wuchen
    Zhou, Haomin
    JOURNAL OF FUNCTIONAL ANALYSIS, 2019, 276 (08) : 2440 - 2469
  • [7] Semi-discrete Optimization Through Semi-discrete Optimal Transport: A Framework for Neural Architecture Search
    Nicolás García Trillos
    Javier Morales
    Journal of Nonlinear Science, 2022, 32
  • [8] Semi-discrete Optimization Through Semi-discrete Optimal Transport: A Framework for Neural Architecture Search
    Trillos, Nicolas Garcia
    Morales, Javier
    JOURNAL OF NONLINEAR SCIENCE, 2022, 32 (03)
  • [9] The dynamical Schrodinger problem in abstract metric spaces
    Monsaingeon, Leonard
    Tamanini, Luca
    Vorotnikov, Dmitry
    ADVANCES IN MATHEMATICS, 2023, 426
  • [10] A Trotter product formula for gradient flows in metric spaces
    Philippe Clément
    Jan Maas
    Journal of Evolution Equations, 2011, 11 : 405 - 427