2018/09/19 by Hugo Lavenant, Sebastian Claici, Edward Chien +1
Computer Science · Mathematics · Physics and Astronomy · #Dirichlet distribution #Discrete space #Discrete time and continuous time #Geometric Analysis and Curvature Flows #Interpolation (computer graphics) #Metric (unit) #Probability distribution #Probability measure #Quadratic equation #Space (punctuation) #Statistical Mechanics and Entropy #Topological and Geometric Data Analysis #cs.NA #math.AP #math.NA #math.OC
paper · pdf · doi:10.1145/3272127.3275064
published as SIGGRAPH Asia 2018, Dec 2018, Tokyo, Japan. 37, 2018
arxiv created 2018/09/19 · arxiv updated 2018/09/20 · openalex created_date 2018/09/27 · openalex publication_date 2018/11/28 · openalex updated_date 2026/08/06
We propose a technique for interpolating between probability distributions on discrete surfaces, based on the theory of optimal transport. Unlike previous attempts that use linear programming, our method is based on a dynamical formulation of quadratic optimal transport proposed for flat domains by Benamou and Brenier [2000], adapted to discrete surfaces. Our structure-preserving construction yields a Riemannian metric on the (finite-dimensional) space of probability distributions on a discrete surface, which translates the so-called Otto calculus to discrete language. From a practical perspective, our technique provides a smooth interpolation between distributions on discrete surfaces with less diffusion than state-of-the-art algorithms involving entropic regularization. Beyond interpolation, we show how our discrete notion of optimal transport extends to other tasks, such as distribution-valued Dirichlet problems and time integration of gradient flows.