A fast approach to optimal transport: the back-and-forth method
From MaRDI portal
Publication:2209529
DOI10.1007/S00211-020-01154-8zbMATH Open1451.65078arXiv1905.12154OpenAlexW3092249998MaRDI QIDQ2209529FDOQ2209529
Authors: Matthew Jacobs, Flavien Léger 
Publication date: 2 November 2020
Published in: Numerische Mathematik (Search for Journal in Brave)
Abstract: We present an iterative method to efficiently solve the optimal transportation problem for a class of strictly convex costs which includes quadratic and p-power costs. Given two probability measures supported on a discrete grid with n points, we compute the optimal map using O(n) storage space and O(n log(n)) operations per iteration, with an approximately exponential convergence rate. Our approach allows us to solve optimal transportation problems on spatial grids as large as 4096x4096 and 384x384x384 in a matter of minutes.
Full work available at URL: https://arxiv.org/abs/1905.12154
Recommendations
- Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
- Optimal transport via a Monge-Ampère optimization problem
- Optimal transport with proximal splitting
- Optimal transport: fast probabilistic approximation with exact solvers
- A geometric variational framework for computing optimal transportation maps. I
Numerical optimization and variational techniques (65K10) Optimal transportation (49Q22) Numerical methods involving duality (49M29) Duality theory (optimization) (49N15)
Cites Work
- Faster than the fast Legendre transform, the linear-time Legendre transform
- The geometry of optimal transportation
- Introductory lectures on convex optimization. A basic course.
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Polar factorization and monotone rearrangement of vector‐valued functions
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- Mean field games
- Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle
- THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
- The Variational Formulation of the Fokker--Planck Equation
- Title not available (Why is that?)
- Minimization of functions having Lipschitz continuous first partial derivatives
- Optimal mass transport for registration and warping
- Numerical solution of the optimal transportation problem using the Monge-Ampère equation
- Fast Legendre–Fenchel Transform and Applications to Hamilton–Jacobi Equations and Conservation Laws
- The auction algorithm for the transportation problem
- An elementary proof of the polar factorization of vector-valued functions
- A combinatorial algorithm for the Euler equations of incompressible flows
Cited In (31)
- A comparison of two dual methods for discrete optimal transport
- An algorithm for optimal transport between a simplex soup and a point cloud
- Darcy's law with a source term
- Efficient and exact multimarginal optimal transport with pairwise costs
- Optrans: a parallel software library for optimal transport
- Fast transport optimization for Monge costs on the circle
- Generalized unnormalized optimal transport and its fast algorithms
- Local matching indicators for concave transport costs
- Matrix Balancing Based Interior Point Methods for Point Set Matching Problems
- Computational Methods for First-Order Nonlocal Mean Field Games with Applications
- Fast entropic regularized optimal transport using semidiscrete cost approximation
- Multiscale strategies for computing optimal transport
- A simple method for the optimal transportation
- Quantitative assessment of hippocampal network dynamics by combining voltage sensitive dye imaging and optimal transportation theory
- Optimal Transport for Parameter Identification of Chaotic Dynamics via Invariant Measures
- An iterative scheme for solving the optimal transportation problem
- Wasserstein archetypal analysis
- Preconditioning of optimal transport
- A sparse multiscale algorithm for dense optimal transport
- The back-and-forth method for Wasserstein gradient flows
- Coupling matrix manifolds assisted optimization for optimal transport problems
- An Optimal Transport Analogue of the Rudin–Osher–Fatemi Model and Its Corresponding Multiscale Theory
- Weak solutions to the Muskat problem with surface tension via optimal transport
- Splitting methods for a class of non-potential mean field games
- Information geometry of Wasserstein statistics on shapes and affine deformations
- No-collision transportation maps
- Discrete optimal transport: complexity, geometry and applications
- Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems
- Vector copulas
- Tumor growth with nutrients: Regularity and stability
- Optimal transport with proximal splitting
Uses Software
This page was built for publication: A fast approach to optimal transport: the back-and-forth method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2209529)
