Optimal Transport with Proximal Splitting

Abstract

This article reviews the use of first order convex optimization schemes to solve the discretized dynamic optimal transport problem, initially proposed by Benamou and Brenier. We develop a staggered grid discretization that is well adapted to the computation of the $L^2$ optimal transport geodesic between distributions defined on a uniform spatial grid. We show how proximal splitting schemes can be used to solve the resulting large scale convex optimization problem. A specific instantiation of this method on a centered grid corresponds to the initial algorithm developed by Benamou and Brenier. We also show how more general cost functions can be taken into account and how to extend the method to perform optimal transport on a Riemannian manifold.

SIAM Journal on Imaging Sciences (2013)

References in corpus (2)

• A viscosity solution approach to the Monge-Ampere formulation of the Optimal Transportation Problem
• Multi-marginal optimal transport on Riemannian manifolds

Cited by in corpus (46)

• Imaging with Kantorovich-Rubinstein discrepancy
• Fixed Point Strategies in Data Science
• Proximal methods for stationary Mean Field Games with local couplings
• Scaling Algorithms for Unbalanced Transport Problems
• TrajectoryNet: A Dynamic Optimal Transport Network for Modeling Cellular Dynamics
• Optimal transport mapping via input convex neural networks
• Dynamical Optimal Transport on Discrete Surfaces
• An Interpolating Distance between Optimal Transport and Fisher-Rao
• Diffeomorphic density matching by optimal information transport
• Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections
• Dynamic Cell Imaging in PET with Optimal Transport Regularization
• Primal dual methods for Wasserstein gradient flows
• Optimal transport via a Monge-Ampère optimization problem
• High order spatial discretization for variational time implicit schemes: Wasserstein gradient flows and reaction-diffusion systems
• Continuous-Flow Graph Transportation Distances
• Bridging Mean-Field Games and Normalizing Flows with Trajectory Regularization
• A numerical algorithm for $L_2$ semi-discrete optimal transport in 3D
• Ground Metric Learning on Graphs
• Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances
• An optimal transport approach for solving dynamic inverse problems in spaces of measures
• Lagrangian schemes for Wasserstein gradient flows
• High order computation of optimal transport, mean field planning, and mean field games
• Generalized conditional gradient: analysis of convergence and applications
• Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• Numerical methods for matching for teams and Wasserstein barycenters
• Entropic Wasserstein Gradient Flows
• A Bilevel Optimization Method for Inverse Mean-Field Games
• Optimal mass transport and kernel density estimation for state-dependent networked dynamic systems
• Iterative Bregman Projections for Regularized Transportation Problems
• Data driven gradient flows
• Optimal perturbations for nonlinear systems using graph-based optimal transport
• Dynamic Optimal Transport with Mixed Boundary Condition for Color Image Processing
• Perspective Functions: Properties, Constructions, and Examples
• Simulation of multiphase porous media flows with minimizing movement and finite volume schemes
• Path constrained unbalanced optimal transport
• Quantitative Stability and Error Estimates for Optimal Transport Plans
• Norm-dependent convergence and stability of the inverse scattering series for diffuse and scalar waves
• Implicit Regularization Effects of the Sobolev Norms in Image Processing
• Consensus-based Distributed Discrete Optimal Transport for Decentralized Resource Matching
• Geodesic Density Tracking with Applications to Data Driven Modeling
• Efficient preconditioners for solving dynamical optimal transport via interior point methods
• A continuation multiple shooting method for Wasserstein geodesic equation
• A Fast Proximal Gradient Method and Convergence Analysis for Dynamic Mean Field Planning
• Solving Coupled Composite Monotone Inclusions by Successive Fejér Approximations of Their Kuhn-Tucker Set
• Breaking the curse of dimension in multi-marginal Kantorovich optimal transport on finite state spaces