A fast approach to optimal transport: the back-and-forth method
From MaRDI portal
Publication:2209529
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.
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
Cites work
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- A combinatorial algorithm for the Euler equations of incompressible flows
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- An elementary proof of the polar factorization of vector-valued functions
- Fast Legendre–Fenchel Transform and Applications to Hamilton–Jacobi Equations and Conservation Laws
- Faster than the fast Legendre transform, the linear-time Legendre transform
- Introductory lectures on convex optimization. A basic course.
- Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle
- Mean field games
- Minimization of functions having Lipschitz continuous first partial derivatives
- Numerical solution of the optimal transportation problem using the Monge-Ampère equation
- Optimal mass transport for registration and warping
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Polar factorization and monotone rearrangement of vector‐valued functions
- THE GEOMETRY OF DISSIPATIVE EVOLUTION EQUATIONS: THE POROUS MEDIUM EQUATION
- The Variational Formulation of the Fokker--Planck Equation
- The auction algorithm for the transportation problem
- The geometry of optimal transportation
Cited in
(45)- No-collision transportation maps
- Wasserstein archetypal analysis
- Matrix Balancing Based Interior Point Methods for Point Set Matching Problems
- A multiscale semi-smooth Newton method for optimal transport
- Optimal transport: fast probabilistic approximation with exact solvers
- A particle-evolving method for approximating the optimal transport plan
- Multiscale strategies for computing optimal transport
- Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems
- Coupling matrix manifolds assisted optimization for optimal transport problems
- An Optimal Transport Analogue of the Rudin–Osher–Fatemi Model and Its Corresponding Multiscale Theory
- Inverse optimal transport
- A comparison of two dual methods for discrete optimal transport
- An iterative scheme for solving the optimal transportation problem
- Weak solutions to the Muskat problem with surface tension via optimal transport
- A simple method for the optimal transportation
- Darcy's law with a source term
- Efficient and exact multimarginal optimal transport with pairwise costs
- Approximating optimal transport with linear programs
- Optimal Transport Approximation of 2-Dimensional Measures
- Tumor growth with nutrients: Regularity and stability
- Fast entropic regularized optimal transport using semidiscrete cost approximation
- Quantitative assessment of hippocampal network dynamics by combining voltage sensitive dye imaging and optimal transportation theory
- The back-and-forth method for Wasserstein gradient flows
- Optrans: a parallel software library for optimal transport
- Fast iterative solution of the optimal transport problem on graphs
- Discrete optimal transport: complexity, geometry and applications
- Optimal transport with proximal splitting
- Preconditioning of optimal transport
- Fast transport optimization for Monge costs on the circle
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
- A geometric variational framework for computing optimal transportation maps. I
- Vector copulas
- Optimal Transport for Parameter Identification of Chaotic Dynamics via Invariant Measures
- Optimal transport between determinantal point processes and application to fast simulation
- Generalized unnormalized optimal transport and its fast algorithms
- Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
- Computational methods for first-order nonlocal mean field games with applications
- Splitting methods for a class of non-potential mean field games
- A sparse multiscale algorithm for dense optimal transport
- A sparse algorithm for dense optimal transport
- An algorithm for optimal transport between a simplex soup and a point cloud
- Local matching indicators for concave transport costs
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Information geometry of Wasserstein statistics on shapes and affine deformations
- <scp>SISTA</scp>: Learning Optimal Transport Costs under Sparsity Constraints
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)
