Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
From MaRDI portal
Abstract: Scaling algorithms for entropic transport-type problems have become a very popular numerical method, encompassing Wasserstein barycenters, multi-marginal problems, gradient flows and unbalanced transport. However, a standard implementation of the scaling algorithm has several numerical limitations: the scaling factors diverge and convergence becomes impractically slow as the entropy regularization approaches zero. Moreover, handling the dense kernel matrix becomes unfeasible for large problems. To address this, we combine several modifications: A log-domain stabilized formulation, the well-known epsilon-scaling heuristic, an adaptive truncation of the kernel and a coarse-to-fine scheme. This permits the solution of larger problems with smaller regularization and negligible truncation error. A new convergence analysis of the Sinkhorn algorithm is developed, working towards a better understanding of epsilon-scaling. Numerical examples illustrate efficiency and versatility of the modified algorithm.
Recommendations
- A sparse multiscale algorithm for dense optimal transport
- A sparse algorithm for dense optimal transport
- A stable alternative to Sinkhorn's algorithm for regularized optimal transport
- Stochastic regularization for transport equations
- Entropic regularization of continuous optimal transport problems
- Scaling algorithms for unbalanced optimal transport problems
- Domain decomposition for entropy regularized optimal transport
- Sparse finite element approximation of high-dimensional transport-dominated diffusion problems
- Fast entropic regularized optimal transport using semidiscrete cost approximation
- Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
Cites work
- 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 new optimal transport distance on the space of finite Radon measures
- A numerical algorithm for \(L_2\) semi-discrete optimal transport in 3D
- A sparse multiscale algorithm for dense optimal transport
- A transportation \(L^p\) distance for signal analysis
- An interpolating distance between optimal transport and Fisher-Rao metrics
- Asymptotic analysis of the exponential penalty trajectory in linear programming
- Barycenters in the Wasserstein space
- Concerning nonnegative matrices and doubly stochastic matrices
- Convergence of entropic schemes for optimal transport and gradient flows
- Convex analysis and monotone operator theory in Hilbert spaces
- Convex color image segmentation with optimal transport distances
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Dual coordinate step methods for linear network flow problems
- Entropic approximation of Wasserstein gradient flows
- Finding Minimum-Cost Circulations by Successive Approximation
- From the Schrödinger problem to the Monge-Kantorovich problem
- Globally optimal joint image segmentation and shape matching based on Wasserstein modes
- scientific article; zbMATH DE number 6378089 (Why is no real title available?)
- scientific article; zbMATH DE number 2152346 (Why is no real title available?)
- 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
- On the scaling of multidimensional matrices
- Optimal entropy-transport problems and a new Hellinger-Kantorovich distance between positive measures
- Optimal mass transport for registration and warping
- Optimal Transport
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Polar factorization and monotone rearrangement of vector‐valued functions
- Scaling algorithms for unbalanced optimal transport problems
- The auction algorithm: A distributed relaxation method for the assignment problem
- The earth mover's distance as a metric for image retrieval
- The invisible hand algorithm: solving the assignment problem with statistical physics
- The Sinkhorn–Knopp Algorithm: Convergence and Applications
- The Variational Formulation of the Fokker--Planck Equation
- Transport between RGB images motivated by dynamic optimal transport
Cited in
(66)- Unbalanced and partial \(L_1\) Monge-Kantorovich problem: a scalable parallel first-order method
- Computation of optimal transport and related hedging problems via penalization and neural networks
- A stochastic multi-layer algorithm for semi-discrete optimal transport with applications to texture synthesis and style transfer
- Coupling matrix manifolds assisted optimization for optimal transport problems
- Domain decomposition for entropy regularized optimal transport
- Transfer operators from optimal transport plans for coherent set detection
- Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms
- A hierarchically low-rank optimal transport dissimilarity measure for structured data
- A multiscale semi-smooth Newton method for optimal transport
- Learning generative neural networks with physics knowledge
- Stochastic saddle-point optimization for the Wasserstein barycenter problem
- Stability of entropic optimal transport and Schrödinger bridges
- The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
- Optimal transport: discretization and algorithms
- On the computation of Wasserstein barycenters
- No-collision transportation maps
- A stable alternative to Sinkhorn's algorithm for regularized optimal transport
- Sparse approximation of triangular transports. II: The infinite-dimensional case
- Irregularity index for vector-valued morphological operators
- Asymptotic analysis of domain decomposition for optimal transport
- Scaling algorithms for unbalanced optimal transport problems
- Barycenters for the Hellinger-Kantorovich distance over \(\mathbb{R}^d\)
- An entropy minimization approach to second-order variational mean-field games
- A fast globally linearly convergent algorithm for the computation of Wasserstein barycenters
- The Linearized Hellinger--Kantorovich Distance
- Empirical regularized optimal transport: statistical theory and applications
- Randomized Wasserstein barycenter computation: resampling with statistical guarantees
- Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems
- Entropic Regularization of NonGradient Systems
- On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
- Inverse optimal transport
- A tumor growth model of Hele-Shaw type as a gradient flow
- The Wasserstein-Fisher-Rao Metric for Waveform Based Earthquake Location
- Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
- Optimal transportation, modelling and numerical simulation
- The GenCol Algorithm for High-Dimensional Optimal Transport: General Formulation and Application to Barycenters and Wasserstein Splines
- Nonequispaced fast Fourier transform boost for the Sinkhorn algorithm
- Entropic optimal transport solutions of the semigeostrophic equations
- Learning to generate Wasserstein barycenters
- Matrix Balancing Based Interior Point Methods for Point Set Matching Problems
- Wassmap: Wasserstein Isometric Mapping for Image Manifold Learning
- Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
- Dynamic programming in probability spaces via optimal transport
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
- Linearized optimal transport on manifolds
- Efficient and exact multimarginal optimal transport with pairwise costs
- Randomized methods for computing optimal transport without regularization and their convergence analysis
- Unbalanced optimal transport and maximum mean discrepancies: interconnections and rapid evaluation
- Wasserstein medians: robustness, PDE characterization, and numerics
- A note on the radiant formula and its relations to the sliced Wasserstein distance
- On the geometry and dynamical formulation of the Sinkhorn algorithm for optimal transport
- Approximation of splines in Wasserstein spaces
- Convergence proof for the GenCol algorithm in the case of two-marginal optimal transport
- Stability and sample complexity of divergence regularized optimal transport
- Sparse Wasserstein barycenters and application to reduced order modeling
- Interpolating between optimal transport and KL regularized optimal transport using Rényi divergences
- Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm
- Transport dependency: optimal transport based dependency measures
- Manifold learning in Wasserstein space
- Quadratically regularized optimal transport: existence and multiplicity of potentials
- Optimal transport-based displacement interpolation with data augmentation for reduced order modeling of nonlinear dynamical systems
- Approximation theory, computing, and deep learning on the Wasserstein space
- A sparse smoothing Newton method for solving discrete optimal transport problems
- Domain decomposition for entropic unbalanced optimal transport
- Entropic transfer operators for stochastic systems
This page was built for publication: Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230605)
