$W_{1,+}$-interpolation of probability measures on graphs

Erwan Hillion (University of Luxembourg)

Abstract


We generalize an equation introduced by Benamou and Brenier and characterizing Wasserstein Wp-geodesics for p > 1, from the continuous setting of probability distributions on a Riemannian manifold to the discrete setting of probability distributions on a general graph. Given an initial and a nal distributions (f_0(x)), (f_1(x)), we prove the existence of a curve (f_t(x)) satisfying this Benamou-Brenier equation. We also show that such a curve can be described as a mixture of binomial distributions with respect to a coupling that is solution of a certain optimization problem.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-29

Publication Date: October 3, 2014

DOI: 10.1214/EJP.v19-3336

References

  • Ambrosio, Luigi; Gigli, Nicola; Savaré, Giuseppe. Gradient flows in metric spaces and in the space of probability measures. Second edition. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2008. x+334 pp. ISBN: 978-3-7643-8721-1 MR2401600
  • Ambrosio, Luigi; Gigli, Nicola; Savaré, Giuseppe. Heat flow and calculus on metric measure spaces with Ricci curvature bounded below—the compact case. Boll. Unione Mat. Ital. (9) 5 (2012), no. 3, 575--629. MR3051737
  • Benamou, Jean-David; Brenier, Yann. A numerical method for the optimal time-continuous mass transport problem and related problems. Monge Ampère equation: applications to geometry and optimization (Deerfield Beach, FL, 1997), 1--11, Contemp. Math., 226, Amer. Math. Soc., Providence, RI, 1999. MR1660739
  • Benamou, Jean-David; Brenier, Yann. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84 (2000), no. 3, 375--393. MR1738163
  • Matthias Erbar, Kazumasa Kuwada, and Karl-Theodor Sturm. On the equivalence of the entropic curvature-dimension condition and bochner's inequality on metric measure spaces. arXiv preprint arXiv:1303.4382, 2013.
  • Erbar, Matthias; Maas, Jan. Ricci curvature of finite Markov chains via convexity of the entropy. Arch. Ration. Mech. Anal. 206 (2012), no. 3, 997--1038. MR2989449
  • Gozlan, Nathael; Roberto, Cyril; Samson, Paul-Marie; Tetali, Prasad. Displacement convexity of entropy and related inequalities on graphs. Probab. Theory Related Fields 160 (2014), no. 1-2, 47--94. MR3256809
  • Erwan Hillion. Contraction of measures on graphs. Potential Analysis, 1--20, 2012.
  • Harremoës, Peter; Johnson, Oliver; Kontoyiannis, Ioannis. Thinning, entropy, and the law of thin numbers. IEEE Trans. Inform. Theory 56 (2010), no. 9, 4228--4244. MR2807322
  • Christian Léonard. On the convexity of the entropy along entropic interpolations. arXiv preprint, 1310.1274.
  • Christian Léonard. Lazy random walks and optimal transport on graphs. arXiv preprint, 1308.0226.
  • Léonard, Christian. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Contin. Dyn. Syst. 34 (2014), no. 4, 1533--1574. MR3121631
  • Lott, John; Villani, Cédric. Ricci curvature for metric-measure spaces via optimal transport. Ann. of Math. (2) 169 (2009), no. 3, 903--991. MR2480619
  • Ollivier, Yann. Ricci curvature of Markov chains on metric spaces. J. Funct. Anal. 256 (2009), no. 3, 810--864. MR2484937
  • Otto, F.; Villani, C. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. J. Funct. Anal. 173 (2000), no. 2, 361--400. MR1760620
  • Sturm, Karl-Theodor. On the geometry of metric measure spaces. I. Acta Math. 196 (2006), no. 1, 65--131. MR2237206
  • Sturm, Karl-Theodor. On the geometry of metric measure spaces. II. Acta Math. 196 (2006), no. 1, 133--177. MR2237207
  • Villani, Cédric. Topics in optimal transportation. Graduate Studies in Mathematics, 58. American Mathematical Society, Providence, RI, 2003. xvi+370 pp. ISBN: 0-8218-3312-X MR1964483
  • Villani, Cédric. Optimal transport. Old and new. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 338. Springer-Verlag, Berlin, 2009. xxii+973 pp. ISBN: 978-3-540-71049-3 MR2459454
  • Yaming Yu and Oliver Johnson. Concavity of entropy under thinning. In Information Theory, 2009. ISIT 2009. IEEE International Symposium on, pages 144--148. IEEE, 2009.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.