A sparse multiscale algorithm for dense optimal transport
From MaRDI portal
Publication:334276
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
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- 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
- 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 Transport
- Optimal mass transport for registration and warping
- Optimal mass transportation and Mather theory
- 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
(43)- Density estimation of multivariate samples using Wasserstein distance
- A transportation \(L^p\) distance for signal analysis
- A multiscale semi-smooth Newton method for optimal transport
- Approximation of optimal transport problems with marginal moments constraints
- Minimal convex extensions and finite difference discretisation of the quadratic Monge-Kantorovich problem
- Optimal transport: fast probabilistic approximation with exact solvers
- A particle-evolving method for approximating the optimal transport plan
- Regularized optimal transport and the rot mover's distance
- Randomized Wasserstein barycenter computation: resampling with statistical guarantees
- Multiscale strategies for computing optimal transport
- Empirical optimal transport on countable metric spaces: distributional limits and statistical applications
- Optimal transport: discretization and algorithms
- Image labeling based on graphical models using Wasserstein messages and geometric assignment
- Unbalanced optimal transport and maximum mean discrepancies: interconnections and rapid evaluation
- Domain decomposition for entropy regularized optimal transport
- Applications of No-Collision Transportation Maps in Manifold Learning
- A stochastic multi-layer algorithm for semi-discrete optimal transport with applications to texture synthesis and style transfer
- A convergent finite difference method for optimal transport on the sphere
- Empirical regularized optimal transport: statistical theory and applications
- Convergence of entropic schemes for optimal transport and gradient flows
- An efficient algorithm for matrix-valued and vector-valued optimal mass transport
- A framework for Wasserstein-1-type metrics
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- Optimal transport via a Monge-Ampère optimization problem
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
- An Interior Point–Inspired Algorithm for Linear Programs Arising in Discrete Optimal Transport
- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- Error bounds for discretized optimal transport and its reliable efficient numerical solution
- Scaling algorithms for unbalanced optimal transport problems
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
- Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning
- Sparse approximation of triangular transports. II: The infinite-dimensional case
- A hierarchically low-rank optimal transport dissimilarity measure for structured data
- A graph space optimal transport distance as a generalization of L p distances: application to a seismic imaging inverse problem
- A sparse algorithm for dense optimal transport
- Traversing the Schrödinger bridge strait: Robert Fortet's marvelous proof redux
- A convergence framework for optimal transport on the sphere
- On coupling particle filter trajectories
- Convex histogram-based joint image segmentation with regularized optimal transport cost
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Moment-SoS methods for 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)
