NDLI: Entropic Approximation of Wasserstein Gradient Flows

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Peyré, Gabriel
Copyright Year	2015
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 nonlinear 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 Kullback--Leibler divergence, which is easier to deal with numerically. We show how Kullback--Leibler first order 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 the Gibbs kernel $e^{-c/\gamma}$, where $c$ is the ground cost and $\gamma>0$ the regularization strength. On Euclidean domains discretized on a 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 nonconvex) 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. We show numerical illustrations of this method to approximate crowd motions with congestion on complicated domains as well as extensions to take into account interactions between multiple densities.
Starting Page	2323
Ending Page	2351
Page Count	29
File Format	PDF
DOI	10.1137/15M1010087
e-ISSN	19364954
Journal	SIAM Journal on Imaging Sciences (SJISBI)
Issue Number	4
Volume Number	8
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2015-10-20
Access Restriction	Subscribed
Subject Keyword	nonlinear diffusion Image processing Kullback--Leibler divergence crowd motion optimal transport Wasserstein distance gradient flow JKO flow Dykstra's algorithm Convex programming
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in