Quadratically regularized optimal transport
From MaRDI portal
Publication:2041024
Abstract: We investigate the problem of optimal transport in the so-called Kantorovich form, i.e. given two Radon measures on two compact sets, we seek an optimal transport plan which is another Radon measure on the product of the sets that has these two measures as marginals and minimizes a certain cost function. We consider quadratic regularization of the problem, which forces the optimal transport plan to be a square integrable function rather than a Radon measure. We derive the dual problem and show strong duality and existence of primal and dual solutions to the regularized problem. Then we derive two algorithms to solve the dual problem of the regularized problem: A Gauss-Seidel method and a semismooth quasi-Newton method and investigate both methods numerically. Our experiments show that the methods perform well even for small regularization parameters. Quadratic regularization is of interest since the resulting optimal transport plans are sparse, i.e. they have a small support (which is not the case for the often used entropic regularization where the optimal transport plan always has full measure).
Recommendations
- Quadratically regularized optimal transport on graphs
- Regularized discrete optimal transport
- Semidual regularized optimal transport
- A geometric perspective on regularized optimal transport
- Optimal transportation for a quadratic cost with convex constraints and applications
- Regularized optimal transport and the rot mover's distance
- Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
- Optimal transport with proximal splitting
- Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach
Cites work
- A smoothed dual approach for variational Wasserstein problems
- Computational optimal transport. With applications to data sciences
- Convergence of entropic schemes for optimal transport and gradient flows
- Coordinate descent algorithms
- Entropic regularization of continuous optimal transport problems
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 3099866 (Why is no real title available?)
- Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
- Modelling and optimisation of flows on networks. Cetraro, Italy 2009. Papers based on the presentations at the CIME course, June 15--19, 2009
- Modern methods in the calculus of variations. L^p spaces
- Nonlinear programming
- On convergence of SOR methods for nonsmooth equations
- Optimal Transport
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Optimal transport with proximal splitting
- Optimization with PDE Constraints
- Quadratically regularized optimal transport on graphs
- Smoothing Methods and Semismooth Methods for Nondifferentiable Operator Equations
- Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations
Cited in
(38)- Computations of optimal transport distance with Fisher information regularization
- Kantorovich problems with a parameter and density constraints
- Orlicz space regularization of continuous optimal transport problems
- Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach
- Second-order models for optimal transport and cubic splines on the Wasserstein Space
- A stable alternative to Sinkhorn's algorithm for regularized optimal transport
- Quadratically regularized optimal transport on graphs
- A sparse algorithm for dense optimal transport
- Semidual regularized optimal transport
- Regularized optimal transport and the rot mover's distance
- Empirical regularized optimal transport: statistical theory and applications
- Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
- Quantum entropic regularization of matrix-valued optimal transport
- A stochastic Gauss–Newton algorithm for regularized semi-discrete optimal transport
- Gaussian approximation for penalized Wasserstein barycenters
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- The dynamical Schrödinger problem in abstract metric spaces
- Bilevel optimal transport problems: existence, regularization and convergence
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
- Hausdorff distances between couplings and optimal transportation
- Algorithms for Euclidean-regularised optimal transport
- Bilevel optimization of the Kantorovich problem and its quadratic regularization. II: Convergence analysis
- Uniform approximation of continuous couplings
- Stability and sample complexity of divergence regularized optimal transport
- Interpolating between optimal transport and KL regularized optimal transport using Rényi divergences
- Sparsity of quadratically regularized optimal transport: bounds on concentration and bias
- Quantum optimal transport with convex regularization
- An Eulerian approach to regularized JKO scheme with low-rank tensor decompositions for Bayesian inversion
- Monotonicity in quadratically regularized linear programs
- Bilevel optimization of the Kantorovich problem and its quadratic regularization
- Quantitative convergence of quadratically regularized linear programs
- Quadratically regularized optimal transport: existence and multiplicity of potentials
- Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs
- Optimal transport and Wasserstein distances for causal models
- Criticality measure-based error estimates for infinite dimensional optimization
- Sparsification techniques for large-scale optimal transport problems
- Well-posedness and efficient algorithms for inverse optimal transport with Bregman regularization
- Sparsity of quadratically regularized optimal transport: scalar case
This page was built for publication: Quadratically regularized optimal transport
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2041024)
