Lazy random walks and optimal transport on graphs

DOI10.1214/15-AOP1012zbMATH Open1397.60109arXiv1308.0226OpenAlexW2964328909MaRDI QIDQ726796FDOQ726796

Christian Léonard

Publication date: 14 July 2016

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: This paper is about the construction of displacement interpolations on a discrete metric graph. Our approach is based on the approximation of any optimal transport problem whose cost function is a distance on a discrete graph by a sequence of Schr"odinger problems associated with random walks whose jump frequencies tend down to zero. Displacement interpolations are defined as the limit of the time-marginal flows of the solutions to the Schr"odinger problems. This allows to work with these interpolations by doing stochastic calculus on the approximating random walks which are regular objects, and then to pass to the limit in a slowing down procedure. The main convergence results are based on Gamma-convergence of entropy minimization problems. As a by-product, we obtain new results about optimal transport on graphs.

Full work available at URL: https://arxiv.org/abs/1308.0226

zbMATH Keywords

optimal transport\(\Gamma\)-convergencerandom walks[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Schr%EF%BF%BD%EF%BF%BDdinger+problem&go=Go Schr��dinger problem]entropy minimizationdiscrete metric graphdisplacement interpolation

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Variational problems in a geometric measure-theoretic setting (49Q20) Sums of independent random variables; random walks (60G50) Methods involving semicontinuity and convergence; relaxation (49J45) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs
• Optimal Transport
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• An introduction to \(\Gamma\)-convergence
• A convexity principle for interacting gases
• Ricci curvature for metric-measure spaces via optimal transport
• On the geometry of metric measure spaces. I
• On the geometry of metric measure spaces. II
• The Monge problem in \(\mathbb R^d\)
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of finite Markov chains via convexity of the entropy
• Asymptotic development by \(\Gamma{}\)-convergence
• A gradient structure for reaction–diffusion systems and for energy-drift-diffusion systems
• From the Schrödinger problem to the Monge-Kantorovich problem
• Gradient flows of the entropy for finite Markov chains
• Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
• Concavity of entropy along binomial convolutions
• Contraction of measures on graphs
• Displacement convexity of entropy and related inequalities on graphs
• Viscosity Solutions of Minimization Problems
• Log-concavity and the maximum entropy property of the Poisson distribution
• Transport inequalities, gradient estimates, entropy and Ricci curvature
• A survey of the Schrödinger problem and some of its connections with optimal transport
• A Riemannian interpolation inequality à la Borell, Brascamp and Lieb
• Mass transportation and rough curvature bounds for discrete spaces
• Existence of optimal transport maps for crystalline norms
• Differential equations methods for the Monge-Kantorovich mass transfer problem
• Girsanov Theory Under a Finite Entropy Condition
• Reciprocal processes. A measure-theoretical point of view
• A Curved Brunn--Minkowski Inequality on the Discrete Hypercube, Or: What Is the Ricci Curvature of the Discrete Hypercube?
• Some Properties of Path Measures

Cited In (16)

• The Most Likely Evolution of Diffusing and Vanishing Particles: Schrödinger Bridges with Unbalanced Marginals
• Some recent developments in functional inequalities
• A transport process on graphs and its limiting distributions
• Entropic Ricci Curvature for Discrete Spaces
• Absolutely continuous and BV-curves in 1-Wasserstein spaces
• Dynamical Schrödinger bridge problems on graphs
• Stochastic Control Liaisons: Richard Sinkhorn Meets Gaspard Monge on a Schrödinger Bridge
• Nonexponential Sanov and Schilder theorems on Wiener space: BSDEs, Schrödinger problems and control
• A survey of the Schrödinger problem and some of its connections with optimal transport
• A second order equation for Schrödinger bridges with applications to the hot gas experiment and entropic transportation cost
• The Markov-quantile process attached to a family of marginals
• Propagation of chaos for mean field Schrödinger problems
• LAZY RANDOM WALKS ON PSEUDOFRACTAL SCALE-FREE WEB WITH A PERFECT TRAP
• Vector-Valued Optimal Mass Transport
• Entropic curvature on graphs along Schrödinger bridges at zero temperature
• What is a stochastic Hamiltonian process on finite graph? An optimal transport answer

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Random walks on graphs: ideas, techniques and results 👍 👎
• Optimal transport between random measures 👍 👎
• Optimal Transport on Networks 👍 👎
• A transport process on graphs and its limiting distributions 👍 👎
• Random Walks on Dense Graphs and Graphons 👍 👎
• Random walks on graphs and approximation of \(L^2\)-invariants 👍 👎
• Optimal Mass Transport on Metric Graphs 👍 👎

This page was built for publication: Lazy random walks and optimal transport on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726796)