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 sciences
- 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 problem via primal-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 (28)
- A hierarchically low-rank optimal transport dissimilarity measure for structured data
- Fast Sinkhorn. I: An \(O(N)\) algorithm for the Wasserstein-1 metric
- The maximum nearby flow problem
- A fast proximal gradient method and convergence analysis for dynamic mean field planning
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Fast entropic regularized optimal transport using semidiscrete cost approximation
- Multiscale strategies for computing optimal transport
- A second-order numerical method for the aggregation equations
- Pattern recognition in data as a diagnosis tool
- Algorithms for optimal transport and Wasserstein distances
- 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
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- A Scalable Deep Learning Approach for Solving High-Dimensional Dynamic Optimal Transport
- On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
- A mean field game inverse problem
- The Wasserstein metric matrix and its computational property
- Optimal transport: fast probabilistic approximation with exact solvers
- 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
- Image segmentation via \(L_1\) Monge-Kantorovich problem
- Linearized Wasserstein dimensionality reduction with approximation guarantees
- An algorithm to approximate the optimal expected inner product of two vectors with given marginals
- 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
- Computations of optimal transport distance with Fisher information regularization
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)
