A fast approach to optimal transport: the back-and-forth method
From MaRDI portal
(Redirected from 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)- A comparison of two dual methods for discrete optimal transport
- Approximating optimal transport with linear programs
- An algorithm for optimal transport between a simplex soup and a point cloud
- Darcy's law with a source term
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Optrans: a parallel software library for optimal transport
- A particle-evolving method for approximating the optimal transport plan
- Efficient and exact multimarginal optimal transport with pairwise costs
- A sparse algorithm for dense optimal transport
- Local matching indicators for concave transport costs
- Generalized unnormalized optimal transport and its fast algorithms
- Optimal transport between determinantal point processes and application to fast simulation
- Fast transport optimization for Monge costs on the circle
- Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
- Matrix Balancing Based Interior Point Methods for Point Set Matching Problems
- Fast entropic regularized optimal transport using semidiscrete cost approximation
- <scp>SISTA</scp>: Learning Optimal Transport Costs under Sparsity Constraints
- Multiscale strategies for computing optimal transport
- A multiscale semi-smooth Newton method for 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
- Inverse optimal transport
- An iterative scheme for solving the optimal transportation problem
- Optimal transport: fast probabilistic approximation with exact solvers
- Wasserstein archetypal analysis
- A sparse multiscale algorithm for dense optimal transport
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
- Preconditioning of optimal transport
- Optimal Transport Approximation of 2-Dimensional Measures
- 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
- A geometric variational framework for computing optimal transportation maps. I
- Computational methods for first-order nonlocal mean field games with applications
- Weak solutions to the Muskat problem with surface tension via optimal transport
- Splitting methods for a class of non-potential mean field games
- Fast iterative solution of the optimal transport problem on graphs
- Information geometry of Wasserstein statistics on shapes and affine deformations
- No-collision transportation maps
- Discrete optimal transport: complexity, geometry and applications
- Vector copulas
- Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems
- Optimal transport with proximal splitting
- Tumor growth with nutrients: Regularity and stability
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)
