Entropic Wasserstein Gradient Flows

Gabriel PeyréarXiv 2015 · DOI · arXiv

Abstract

This article presents a novel numerical scheme designed to approximate gradient flows within the Wasserstein space. These flows are essential for modeling non-linear diffusion processes, such as porous media evolution and crowd dynamics. While the Jordan-Kinderlehrer-Otto (JKO) scheme provides a theoretical foundation for these evolutions via implicit Euler time-stepping, the computational cost of solving the underlying optimal transport (OT) problem has historically limited its application. By introducing entropic regularization, we transform the OT problem into a Kullback-Leibler (KL) proximal problem. This allows for the use of Dykstra’s algorithm, resulting in a fast, parallelizable scheme that leverages Gibbs kernel multiplications—implemented as Gaussian filtering on grids or short-time heat diffusion on manifolds.

1. Introduction

The study of density evolutions through gradient flows in the Wasserstein space—often referred to as the JKO scheme—has emerged as a powerful framework for understanding non-linear diffusion. These models are pivotal in describing physical and social phenomena, ranging from gas filtration in porous media to the collective behavior of human crowds. However, the practical utility of the JKO scheme is frequently hampered by the immense computational burden of its discrete steps. Each iteration requires solving a convex optimization problem involving the Wasserstein distance, a task that scales poorly with the resolution of the domain.

2. The Computational Bottleneck of Optimal Transport

In the standard JKO framework, the evolution of a density $\rho$ is discretized in time. At each step, one must find a new density that minimizes the sum of an energy functional (representing physics like internal energy or potential) and the squared Wasserstein distance to the previous state. This distance represents the "effort" required to move mass. Solving this transport problem traditionally involves complex linear programming or specialized solvers that are too slow for high-resolution 2D/3D grids or complex geometric manifolds, making large-scale simulations nearly impossible.

3. Entropic Regularization and Dykstra’s Algorithm

To overcome these limitations, this research proposes a shift toward entropic regularization. By adding an entropy penalty to the transportation coupling, the optimal transport problem is smoothed and becomes strictly convex.

3.1 From Wasserstein to Kullback-Leibler

The key advantage of this regularization is that it allows the fidelity term to be recast as a Kullback-Leibler (KL) divergence. KL-based proximal schemes are significantly more tractable than their pure OT counterparts. The author utilizes an extension of Dykstra’s algorithm—a classic iterative method for finding the intersection of convex sets—to solve the regularized JKO step. This approach allows the algorithm to handle complex energy functionals, including non-smooth constraints like density caps in congestion models, through closed-form proximal operators.

3.2 The Gibbs Kernel Trick

The most computationally intensive part of the algorithm is reduced to matrix-vector multiplications with a Gibbs kernel ($e^{-c/\gamma}$). The implementation varies based on the domain:

  • Euclidean Grids: On uniform grids, this operation is equivalent to a Gaussian blur, which can be computed in nearly linear time using Fast Fourier Transforms (FFTs) or recursive filtering.
  • Complex Manifolds: On non-convex shapes or triangular meshes, the Gibbs kernel is approximated via short-time heat diffusion. This allows the scheme to respect the geometry of the domain without explicitly computing expensive geodesic distances.

4. Applications and Empirical Results

The versatility of the entropic scheme is demonstrated across several challenging scenarios using benchmarks such as 200x200 uniform grids and 20,000-vertex 3D meshes:

  • Crowd Dynamics and Congestion: The framework naturally incorporates density constraints. In simulations of crowds moving through bottlenecks, the model accurately captures the accumulation of mass behind narrow openings, a hallmark of real-world congestion that simple linear diffusion fails to represent.
  • Porous Media Equations: The algorithm successfully reproduces the "sharp front" behavior characteristic of the porous medium equation. Unlike standard diffusion, which spreads mass infinitely thin, this model maintains the compact support of the density over time.
  • Anisotropic and Manifold Flows: By adjusting the kernel, the author demonstrates "steerable" diffusion following specific vector fields (e.g., wind currents). Furthermore, simulations on complex 3D meshes (such as the "fertility" statue) show that the method remains robust on non-Euclidean surfaces.

5. Discussion and Limitations

While the entropic approach offers a massive leap in efficiency—achieving nearly linear time complexity—it introduces a "blurring" bias controlled by the regularization parameter $\gamma$. A large $\gamma$ speeds up convergence but loses transport precision, while a very small $\gamma$ can lead to numerical instability. Additionally, while the method works well for many energy functionals, formal convergence guarantees for highly non-convex constraints remain an area for future research. Finally, because the entropic "distance" is not a true metric (it does not satisfy $W_\gamma(p,p)=0$), the steady states of the flow may appear slightly more diffused than their theoretical counterparts.

6. Conclusion

By marrying entropic regularization with proximal splitting techniques, this work provides a scalable and versatile toolkit for simulating complex non-linear diffusions. The ability to handle high-resolution grids and arbitrary manifolds opens new doors for applications in computer vision, physics-based animation, and urban planning.

Summary updated

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.
BibTeX
@misc{peyre2015entropic,
  author = {Gabriel Peyré},
  title = {{Entropic Wasserstein Gradient Flows}},
  year = {2015},
  eprint = {1502.06216},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.06216},
}
Figure