Name
Abstract | ||
|---|---|---|
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 $$\Gamma $$-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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00211-019-01077-z | Numerische Mathematik |
Keywords | Field | DocType |
Optimal transport on graphs, Proximal splitting, Gradient flows, 65K10, 49M29, 49Q20, 60J27 | Discretization,Slack variable,Mathematical analysis,Markov chain,Logarithmic mean,Semigroup,Backward Euler method,Balanced flow,Mathematics,Discrete space | Journal |
Volume | Issue | ISSN |
144 | 1 | 0029-599X |
Citations | PageRank | References |
4 | 0.41 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias Erbar | 1 | 4 | 0.41 |
| Martin Rumpf | 2 | 230 | 18.97 |
| Bernhard Schmitzer | 3 | 76 | 8.22 |
| Stefan Simon | 4 | 4 | 0.41 |