A sparse multiscale algorithm for dense optimal transport
From MaRDI portal
Publication:334276
DOI10.1007/S10851-016-0653-9zbMATH Open1351.49037arXiv1510.05466OpenAlexW2211336473MaRDI QIDQ334276FDOQ334276
Authors: Bernhard Schmitzer 
Publication date: 1 November 2016
Published in: Journal of Mathematical Imaging and Vision (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1510.05466
Recommendations
Cites Work
- Network flows. Theory, algorithms, and applications.
- The earth mover's distance as a metric for image retrieval
- Convex analysis and monotone operator theory in Hilbert spaces
- The geometry of optimal transportation
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Polar factorization and monotone rearrangement of vector‐valued functions
- Title not available (Why is that?)
- Optimal Transport
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- Polar factorization of maps on Riemannian manifolds
- A class of Cartesian grid embedded boundary algorithms for incompressible flow with time-varying complex geometries
- Finding Minimum-Cost Circulations by Successive Approximation
- Iterative Bregman projections for regularized transportation problems
- Perspectives of Monge properties in optimization
- Optimal mass transport for registration and warping
- Numerical solution of the optimal transportation problem using the Monge-Ampère equation
- A linear optimal transportation framework for quantifying and visualizing variations in sets of images
- Regularized regression and density estimation based on optimal transport
- From Knothe's Transport to Brenier's Map and a Continuation Method for Optimal Transport
- A sparse algorithm for dense optimal transport
- Transport between RGB images motivated by dynamic optimal transport
- A generalized model for optimal transport of images including dissipation and density modulation
- Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
- Optimal mass transportation and Mather theory
- Globally optimal joint image segmentation and shape matching based on Wasserstein modes
Cited In (41)
- Genetic Column Generation: Fast Computation of High-Dimensional Multimarginal Optimal Transport Problems
- A hierarchically low-rank optimal transport dissimilarity measure for structured data
- Optimal transport: discretization and algorithms
- Empirical Regularized Optimal Transport: Statistical Theory and Applications
- Title not available (Why is that?)
- 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
- Minimal convex extensions and finite difference discretisation of the quadratic Monge–Kantorovich 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
- Moment-SoS methods for optimal transport problems
- Approximation of optimal transport problems with marginal moments constraints
- Empirical optimal transport on countable metric spaces: distributional limits and statistical applications
- 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
- Title not available (Why is that?)
- 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
- A convergence framework for optimal transport on the sphere
- A Framework for Wasserstein-1-Type Metrics
- 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
- Randomized Wasserstein Barycenter Computation: Resampling with Statistical Guarantees
- Error Bounds for Discretized Optimal Transport and Its Reliable Efficient Numerical Solution
- 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
- Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
- Optimal Transport via a Monge--Ampère Optimization Problem
- On coupling particle filter trajectories
- Convex histogram-based joint image segmentation with regularized optimal transport cost
- Multilevel Optimal Transport: A Fast Approximation of Wasserstein-1 Distances
- An efficient algorithm for matrix-valued and vector-valued optimal mass transport
- Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
- Title not available (Why is that?)
- Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment
Uses Software
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)
