Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
From MaRDI portal
(Redirected from Publication:5147991)
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.
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
Cites work
- scientific article; zbMATH DE number 53856 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- A Continuous Model of Transportation
- 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
- A framework for Wasserstein-1-type metrics
- A multilevel method for the solution of time dependent optimal transport
- A numerical solution to Monge’s problem with a Finsler distance as cost
- A parallel method for earth mover's distance
- A smoothed dual approach for variational Wasserstein problems
- A sparse multiscale algorithm for dense optimal transport
- Adaptive approximation of the Monge-Kantorovich problem via primal-dual gap estimates
- Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations
- Computational optimal transport. With applications to data sciences
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convergence of entropic schemes for optimal transport and gradient flows
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Dynamic models of Wasserstein-1-type unbalanced transport
- Earth mover's distances on discrete surfaces
- Fast Fourier transforms: A tutorial review and a state of the art
- Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality
- Iterative Bregman projections for regularized transportation problems
- On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
- On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint
- Optimal Transport
- Optimal Transport Over a Linear Dynamical System
- Optimal transport with proximal splitting
- Quadratically regularized optimal transport on graphs
- Regularized discrete optimal transport
- Solving large-scale optimization problems with a convergence rate independent of grid size
- The cascadic multigrid method for elliptic problems
- The earth mover's distance as a metric for image retrieval
- The geometry of optimal transportation
- Unbalanced and partial \(L_1\) Monge-Kantorovich problem: a scalable parallel first-order method
- Vector and matrix optimal mass transport: theory, algorithm, and applications
Cited in
(30)- 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
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- A fast proximal gradient method and convergence analysis for dynamic mean field planning
- Fast entropic regularized optimal transport using semidiscrete cost approximation
- Pattern recognition in data as a diagnosis tool
- Multiscale strategies for computing optimal transport
- Numerical solution of Monge-Kantorovich equations via a dynamic formulation
- A second-order numerical method for the aggregation equations
- Algorithms for optimal transport and Wasserstein distances
- A multiscale semi-smooth Newton method for optimal transport
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm
- Sampling-based methods for multi-block optimization problems over transport polytopes
- A Scalable Deep Learning Approach for Solving High-Dimensional Dynamic Optimal Transport
- A mean field game inverse problem
- On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
- 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 a generalization of Wasserstein distance and the Beckmann problem to connection graphs
- On the Convergence of Continuous and Discrete Unbalanced Optimal Transport Models for 1-Wasserstein Distance
- scientific article; zbMATH DE number 7415088 (Why is no real title available?)
- Computations of optimal transport distance with Fisher information regularization
- Template-based CT reconstruction with optimal transport and total generalized variation
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)
