Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
From MaRDI portal
Publication:5147991
DOI10.1137/18M1219813zbMATH Open1456.49038arXiv1810.00118MaRDI QIDQ5147991FDOQ5147991
Authors: Jialin Liu, Wotao Yin, Wuchen Li, Yat Tin Chow 
Publication date: 29 January 2021
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: We propose a fast algorithm for the calculation of the Wasserstein-1 distance, which is a particular type of optimal transport distance with homogeneous of degree one transport cost. Our algorithm is built on multilevel primal-dual algorithms. Several numerical examples and a complexity analysis are provided to demonstrate its computational speed. On some commonly used image examples of size , the proposed algorithm gives solutions within seconds on a single CPU, which is much faster than the state-of-the-art algorithms.
Full work available at URL: https://arxiv.org/abs/1810.00118
Recommendations
- Fast Sinkhorn. I: An \(O(N)\) algorithm for the Wasserstein-1 metric
- Algorithms for optimal transport and Wasserstein distances
- Computations of optimal transport distance with Fisher information regularization
- Optimal transport: fast probabilistic approximation with exact solvers
- A fast approach to optimal transport: the back-and-forth method
Optimal transportation (49Q22) Applications of mathematical programming (90C90) Discrete approximations in optimal control (49M25)
Cites Work
- The earth mover's distance as a metric for image retrieval
- Computational Optimal Transport: With Applications to Data Science
- The geometry of optimal transportation
- Title not available (Why is that?)
- Optimal Transport
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Title not available (Why is that?)
- The cascadic multigrid method for elliptic problems
- Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
- Iterative Bregman Projections for Regularized Transportation Problems
- Fast Fourier transforms: A tutorial review and a state of the art
- On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint
- Optimal Transport Over a Linear Dynamical System
- Optimal transport with proximal splitting
- Regularized Discrete Optimal Transport
- Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations
- A sparse multiscale algorithm for dense optimal transport
- A numerical solution to Monge’s problem with a Finsler distance as cost
- A Continuous Model of Transportation
- A parallel method for earth mover's distance
- Earth mover's distances on discrete surfaces
- Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
- A Multilevel Method for the Solution of Time Dependent Optimal Transport
- Vector and Matrix Optimal Mass Transport: Theory, Algorithm, and Applications
- Unbalanced and partial \(L_1\) Monge-Kantorovich problem: a scalable parallel first-order method
- Adaptive approximation of the Monge–Kantorovich problemviaprimal-dual gap estimates
- Quadratically Regularized Optimal Transport on Graphs
- Solving Large-Scale Optimization Problems with a Convergence Rate Independent of Grid Size
- Dynamic models of Wasserstein-1-type unbalanced transport
- A Framework for Wasserstein-1-Type Metrics
- A Smoothed Dual Approach for Variational Wasserstein Problems
- On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows
Cited In (15)
- Fast Sinkhorn. I: An \(O(N)\) algorithm for the Wasserstein-1 metric
- A fast proximal gradient method and convergence analysis for dynamic mean field planning
- Title not available (Why is that?)
- A second-order numerical method for the aggregation equations
- Pattern recognition in data as a diagnosis tool
- Numerical solution of Monge-Kantorovich equations via a dynamic formulation
- Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm
- A multiscale semi-smooth Newton method for optimal transport
- A Scalable Deep Learning Approach for Solving High-Dimensional Dynamic Optimal Transport
- A mean field game inverse problem
- The GenCol Algorithm for High-Dimensional Optimal Transport: General Formulation and Application to Barycenters and Wasserstein Splines
- Weyl law for semi-classical resonances with randomly perturbed potentials
- On the Convergence of Continuous and Discrete Unbalanced Optimal Transport Models for 1-Wasserstein Distance
- Title not available (Why is that?)
- Template-based CT reconstruction with optimal transport and total generalized variation
Uses Software
This page was built for publication: Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5147991)
