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