Entropic approximation of Wasserstein gradient flows

DOI10.1137/15M1010087MaRDI QIDQ3454493zbMATH OpenOpenAlexFDO

Authors Gabriel Peyré

Publication date 25 November 2015

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

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

zbMATH Keywords

crowd motionDykstra's algorithmgradient flowJKO flowKullback-Leibler divergencenonlinear diffusionoptimal transportWasserstein distance

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Convex programming (90C25)

Abstract: This article details a novel numerical scheme to approximate gradient flows for optimal transport (i.e. Wasserstein) metrics. These flows have proved useful to tackle theoretically and numerically non-linear diffusion equations that model for instance porous media or crowd evolutions. These gradient flows define a suitable notion of weak solutions for these evolutions and they can be approximated in a stable way using discrete flows. These discrete flows are implicit Euler time stepping according to the Wasserstein metric. A bottleneck of these approaches is the high computational load induced by the resolution of each step. Indeed, this corresponds to the resolution of a convex optimization problem involving a Wasserstein distance to the previous iterate. Following several recent works on the approximation of Wasserstein distances, we consider a discrete flow induced by an entropic regularization of the transportation coupling. This entropic regularization allows one to trade the initial Wasserstein fidelity term for a Kulback-Leibler divergence, which is easier to deal with numerically. We show how KL proximal schemes, and in particular Dykstra's algorithm, can be used to compute each step of the regularized flow. The resulting algorithm is both fast, parallelizable and versatile, because it only requires multiplications by a Gibbs kernel. On Euclidean domains discretized on an uniform grid, this corresponds to a linear filtering (for instance a Gaussian filtering when $c$ is the squared Euclidean distance) which can be computed in nearly linear time. On more general domains, such as (possibly non-convex) shapes or on manifolds discretized by a triangular mesh, following a recently proposed numerical scheme for optimal transport, this Gibbs kernel multiplication is approximated by a short-time heat diffusion.

Recommendations

• Convergence of entropic schemes for optimal transport and gradient flows
• Fisher information regularization schemes for Wasserstein gradient flows
• Entropic Regularization of NonGradient Systems
• One-dimensional numerical algorithms for gradient flows in the p-Wasserstein spaces
• An augmented Lagrangian approach to Wasserstein gradient flows and applications

Cites work

• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• A finite-volume method for nonlinear nonlocal equations with a gradient flow structure
• A MACROSCOPIC CROWD MOTION MODEL OF GRADIENT FLOW TYPE
• A mixed finite element method for nonlinear diffusion equations
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• A survey of the Schrödinger problem and some of its connections with optimal transport
• An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions
• An iterative procedure for obtaining I-projections onto the intersection of convex sets
• Approximation of Parabolic Equations Using the Wasserstein Metric
• Barycenters in the Wasserstein space
• Characterization of barycenters in the Wasserstein space by averaging optimal transport maps
• Concerning nonnegative matrices and doubly stochastic matrices
• Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation
• Convergence of the Mass-Transport Steepest Descent Scheme for the Subcritical Patlak–Keller–Segel Model
• Convex analysis and monotone operator theory in Hilbert spaces
• Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• Diffusion processes in a small time interval
• Direct Methods for Sparse Linear Systems
• Discretization of functionals involving the Monge-Ampère operator
• Dykstras algorithm with bregman projections: A convergence proof
• Existence of solutions to degenerate parabolic equations via the Monge-Kantorovich theory
• Fast Marching Methods
• Fokker-Planck equations for a free energy functional or Markov process on a graph
• From a large-deviations principle to the Wasserstein gradient flow: a new micro-macro passage
• Geodesic convexity of the relative entropy in reversible Markov chains
• Global convergence of a non-convex Douglas-Rachford iteration
• Gradient flows of the entropy for finite Markov chains
• scientific article; zbMATH DE number 5564093 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1111402 (Why is no real title available?)
• scientific article; zbMATH DE number 1174325 (Why is no real title available?)
• scientific article; zbMATH DE number 3001084 (Why is no real title available?)
• scientific article; zbMATH DE number 2152346 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 1393068 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• I-divergence geometry of probability distributions and minimization problems
• Iterative Bregman projections for regularized transportation problems
• Monge-Ampère based moving mesh methods for numerical weather prediction, with applications to the Eady problem
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• Numerical simulation of diffusive and aggregation phenomena in nonlinear continuity equations by evolving diffeomorphisms
• On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are Known
• On the ergodic convergence rates of a first-order primal-dual algorithm
• On the local structure of optimal measures in the multi-marginal optimal transportation problem
• One-dimensional numerical algorithms for gradient flows in the p-Wasserstein spaces
• Optimal transport and Cournot-Nash equilibria
• Optimal transport with proximal splitting
• Proximal Minimization Methods with Generalized Bregman Functions
• Regularized regression and density estimation based on optimal transport
• Sparse non-negative stencils for anisotropic diffusion
• Synthesizing and mixing stationary Gaussian texture models
• The earth mover's distance as a metric for image retrieval
• THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
• The heat equation on manifolds as a gradient flow in the Wasserstein space
• The Least Action Principle and the Related Concept of Generalized Flows for Incompressible Perfect Fluids
• The optimal partial transport problem
• The Variational Formulation of the Fokker--Planck Equation
• The Wasserstein gradient flow of the Fisher information and the quantum drift-diffusion equation
• Variational particle schemes for the porous medium equation and for the system of isentropic Euler equations

Cited in

(62)

• The Wasserstein gradient flow of the Fisher information and the quantum drift-diffusion equation
• A Lagrangian scheme for the solution of nonlinear diffusion equations using moving simplex meshes
• Numerical analysis of a robust free energy diminishing finite volume scheme for parabolic equations with gradient structure
• A multi-objective interpretation of optimal transport
• A BDF2-approach for the non-linear Fokker-Planck equation
• One-dimensional numerical algorithms for gradient flows in the p-Wasserstein spaces
• A dynamic mass transport method for Poisson-Nernst-Planck equations
• Approximate Wasserstein attraction flows for dynamic mass transport over networks
• Hessian informed mirror descent
• Splitting scheme for a macroscopic crowd motion model with congestion for a two-typed population
• On the Wasserstein distance between mutually singular measures
• Variational problems involving unequal dimensional optimal transport
• A variational finite volume scheme for Wasserstein gradient flows
• Aggregation-diffusion to constrained interaction: minimizers \& gradient flows in the slow diffusion limit
• Geometry of matrix decompositions seen through optimal transport and information geometry
• Numerical simulation of nonlinear continuity equations by evolving diffeomorphisms
• Operator-splitting schemes for degenerate, non-local, conservative-dissipative systems
• A spatial Pareto exchange economy problem
• Contraction of the proximal map and generalized convexity of the Moreau-Yosida regularization in the 2-Wasserstein metric
• A smoothed dual approach for variational Wasserstein problems
• Upscaling from particle models to entropic gradient flows
• A Monotone Approximation to the Wasserstein Diffusion
• Scaling algorithms for unbalanced optimal transport problems
• An augmented Lagrangian approach to Wasserstein gradient flows and applications
• A Diffusion-Driven Characteristic Mapping Method for Particle Management
• Semidual regularized optimal transport
• Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
• Image labeling based on graphical models using Wasserstein messages and geometric assignment
• An entropy minimization approach to second-order variational mean-field games
• The back-and-forth method for Wasserstein gradient flows
• Supervised optimal transport
• Time discretizations of Wasserstein-Hamiltonian flows
• Entropic Regularization of NonGradient Systems
• TPFA finite volume approximation of Wasserstein gradient flows
• Discretization of flux-limited gradient flows: -convergence and numerical schemes
• A variational formulation of the BDF2 method for metric gradient flows
• A smoothed dual approach for variational Wasserstein problems
• Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
• A JKO splitting scheme for Kantorovich-Fisher-Rao gradient flows
• Convergence of entropic schemes for optimal transport and gradient flows
• A tumor growth model of Hele-Shaw type as a gradient flow
• Optimal transportation, modelling and numerical simulation
• Semi-discrete optimal transport: hardness, regularization and numerical solution
• Template-based CT reconstruction with optimal transport and total generalized variation
• Optimal transport with nonlinear mobilities: a deterministic particle approximation result
• Carathéodory theory and a priori estimates for continuity inclusions in the space of probability measures
• From optimal transport to discrepancy
• Variational methods for evolution. Abstracts from the workshop held December 5--8, 2023
• Strong \(L^2 H^2\) convergence of the JKO scheme for the Fokker-Planck equation
• Computation of Cournot-Nash equilibria by entropic regularization
• JKO schemes with general transport costs
• Choquet-Wasserstein pseudo-distances via optimal transport under partially specified marginal probabilities
• Entropic optimal transport with data-driven metrics on the roto-translation group
• An Eulerian approach to regularized JKO scheme with low-rank tensor decompositions for Bayesian inversion
• Structure preserving schemes for a class of Wasserstein gradient flows
• Supervised Gromov-Wasserstein optimal transport with metric-preserving constraints
• Parameterized Wasserstein gradient flow
• Sparsification techniques for large-scale optimal transport problems
• Discretization of functionals involving the Monge-Ampère operator
• A variational formulation of a multi-population mean field games with non-local interactions
• Fisher information regularization schemes for Wasserstein gradient flows
• A mean field game model for the evolution of cities

Describes a project that uses

Uses Software

• BADMM
• CSparse
• EMD

This page was built for publication: Entropic approximation of Wasserstein gradient flows

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