Quadratically regularized optimal transport

DOI10.1007/S00245-019-09614-WzbMATH Open1468.49051arXiv1903.01112OpenAlexW2977099832WikidataQ127205688 ScholiaQ127205688MaRDI QIDQ2041024FDOQ2041024

Authors: Yanyan Li 

Publication date: 15 July 2021

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/1903.01112

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

zbMATH Keywords

regularizationoptimal transportdualityGauss-Seidel methodsemismooth Newton method

Mathematics Subject Classification ID

Convex programming (90C25) Optimal transportation (49Q22) Newton-type methods (49M15) Numerical methods involving duality (49M29) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Cites Work

• Computational optimal transport. With applications to data sciences
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Optimal Transport
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• Modern methods in the calculus of variations. \(L^p\) spaces
• Optimization with PDE Constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coordinate descent algorithms
• Smoothing Methods and Semismooth Methods for Nondifferentiable Operator Equations
• Optimal transport with proximal splitting
• Modelling and optimisation of flows on networks. Cetraro, Italy 2009. Papers based on the presentations at the CIME course, June 15--19, 2009
• On convergence of SOR methods for nonsmooth equations
• Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations
• Convergence of entropic schemes for optimal transport and gradient flows
• Nonlinear programming
• A smoothed dual approach for variational Wasserstein problems
• Entropic regularization of continuous optimal transport problems
• Quadratically regularized optimal transport on graphs

Cited In (24)

• Hausdorff distances between couplings and optimal transportation
• A stochastic Gauss–Newton algorithm for regularized semi-discrete optimal transport
• Semidual regularized optimal transport
• A sparse algorithm for dense optimal transport
• Algorithms for Euclidean-regularised optimal transport
• Bilevel optimization of the Kantorovich problem and its quadratic regularization. II: Convergence analysis
• Orlicz space regularization of continuous optimal transport problems
• Second-order models for optimal transport and cubic splines on the Wasserstein Space
• Quantum entropic regularization of matrix-valued optimal transport
• A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
• Quadratically regularized optimal transport on graphs
• Empirical regularized optimal transport: statistical theory and applications
• Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
• Uniform approximation of continuous couplings
• Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach
• Stability and sample complexity of divergence regularized optimal transport
• A stable alternative to Sinkhorn's algorithm for regularized optimal transport
• Kantorovich problems with a parameter and density constraints
• Bilevel optimal transport problems: existence, regularization and convergence
• The dynamical Schrödinger problem in abstract metric spaces
• Regularized optimal transport and the rot mover's distance
• A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
• Gaussian approximation for penalized Wasserstein barycenters
• Computations of optimal transport distance with Fisher information regularization

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)