A sparse multiscale algorithm for dense optimal transport
From MaRDI portal
Abstract: Discrete optimal transport solvers do not scale well on dense large problems since they do not explicitly exploit the geometric structure of the cost function. In analogy to continuous optimal transport we provide a framework to verify global optimality of a discrete transport plan locally. This allows construction of an algorithm to solve large dense problems by considering a sequence of sparse problems instead. The algorithm lends itself to being combined with a hierarchical multi-scale scheme. Any existing discrete solver can be used as internal black-box.Several cost functions, including the noisy squared Euclidean distance, are explicitly detailed. We observe a significant reduction of run-time and memory requirements.
Recommendations
Cites work
- A class of Cartesian grid embedded boundary algorithms for incompressible flow with time-varying complex geometries
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- A generalized model for optimal transport of images including dissipation and density modulation
- A linear optimal transportation framework for quantifying and visualizing variations in sets of images
- A sparse algorithm for dense optimal transport
- Convex analysis and monotone operator theory in Hilbert spaces
- Finding Minimum-Cost Circulations by Successive Approximation
- From Knothe's Transport to Brenier's Map and a Continuation Method for Optimal Transport
- Globally optimal joint image segmentation and shape matching based on Wasserstein modes
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- Iterative Bregman projections for regularized transportation problems
- Network flows. Theory, algorithms, and applications.
- Numerical solution of the optimal transportation problem using the Monge-Ampère equation
- Optimal mass transport for registration and warping
- Optimal mass transportation and Mather theory
- Optimal Transport
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Perspectives of Monge properties in optimization
- Polar factorization and monotone rearrangement of vector‐valued functions
- Polar factorization of maps on Riemannian manifolds
- Regularized regression and density estimation based on optimal transport
- Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
- The earth mover's distance as a metric for image retrieval
- The geometry of optimal transportation
- Transport between RGB images motivated by dynamic optimal transport
Cited in
(44)- An efficient algorithm for matrix-valued and vector-valued optimal mass transport
- On coupling particle filter trajectories
- Convex histogram-based joint image segmentation with regularized optimal transport cost
- A transportation \(L^p\) distance for signal analysis
- A stochastic multi-layer algorithm for semi-discrete optimal transport with applications to texture synthesis and style transfer
- Domain decomposition for entropy regularized optimal transport
- A hierarchically low-rank optimal transport dissimilarity measure for structured data
- A particle-evolving method for approximating the optimal transport plan
- A convergent finite difference method for optimal transport on the sphere
- A multiscale semi-smooth Newton method for optimal transport
- A convergence framework for optimal transport on the sphere
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
- Optimal transport: discretization and algorithms
- Empirical optimal transport on countable metric spaces: distributional limits and statistical applications
- Traversing the Schrödinger bridge strait: Robert Fortet's marvelous proof redux
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Sparse approximation of triangular transports. II: The infinite-dimensional case
- Scaling algorithms for unbalanced optimal transport problems
- A sparse algorithm for dense optimal transport
- Regularized optimal transport and the rot mover's distance
- Multiscale strategies for computing optimal transport
- Image labeling based on graphical models using Wasserstein messages and geometric assignment
- A framework for Wasserstein-1-type metrics
- Empirical regularized optimal transport: statistical theory and applications
- Error bounds for discretized optimal transport and its reliable efficient numerical solution
- Randomized Wasserstein barycenter computation: resampling with statistical guarantees
- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- Density estimation of multivariate samples using Wasserstein distance
- Approximation of optimal transport problems with marginal moments constraints
- Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
- Optimal transport: fast probabilistic approximation with exact solvers
- A graph space optimal transport distance as a generalization of L p distances: application to a seis
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Minimal convex extensions and finite difference discretisation of the quadratic Monge-Kantorovich problem
- Optimal transport via a Monge-Ampère optimization problem
- Convergence of entropic schemes for optimal transport and gradient flows
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning
- An Interior Point–Inspired Algorithm for Linear Programs Arising in Discrete Optimal Transport
- Applications of No-Collision Transportation Maps in Manifold Learning
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- Moment-SoS methods for optimal transport problems
- Unbalanced optimal transport and maximum mean discrepancies: interconnections and rapid evaluation
- A sparse smoothing Newton method for solving discrete optimal transport problems
This page was built for publication: A sparse multiscale algorithm for dense optimal transport
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334276)
