An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm

DOI10.1007/S10915-020-01325-7zbMATH Open1478.49043arXiv1911.06850OpenAlexW3093980270MaRDI QIDQ2210656FDOQ2210656

Authors: Simone Di Marino, Augusto Gerolin 

Publication date: 7 November 2020

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: This paper exploit the equivalence between the Schr"odinger Bridge problem and the entropy penalized optimal transport in order to find a different approach to the duality, in the spirit of optimal transport. This approach results in a priori estimates which are consistent in the limit when the regularization parameter goes to zero. In particular, we find a new proof of the existence of maximizing entropic-potentials and therefore, the existence of a solution of the Schr"odinger system. Our method extends also when we have more than two marginals: we can provide an alternative proof of the convergence of the Sinkhorn algorithm with two marginals and we show that the Sinkhorn algorithm converges in the multi-marginal case.

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

Recommendations

• Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
• On the relation between optimal transport and Schrödinger bridges: a stochastic control viewpoint
• Entropical optimal transport, Schrödinger's system and algorithms
• Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
• Stability of entropic optimal transport and Schrödinger bridges
• Wasserstein Proximal Algorithms for the Schrödinger Bridge Problem: Density Control With Nonlinear Drift
• The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations
• Optimal transport. A semi-discrete approach
• A convergent finite difference method for optimal transport on the sphere
• A survey of the Schrödinger problem and some of its connections with optimal transport

zbMATH Keywords

Kantorovich dualitySinkhorn algorithmiterative proportional fitting procedureentropic regularization of optimal transportSchrödinger bridge problem

Mathematics Subject Classification ID

Optimal transportation (49Q22) Methods involving semicontinuity and convergence; relaxation (49J45) Numerical methods based on necessary conditions (49M05) Duality theory (optimization) (49N15)

Cites Work

• Convergence of the iterative proportional fitting procedure
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Barycenters in the Wasserstein Space
• Scaling algorithms for unbalanced optimal transport problems
• Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
• Optimal maps for the multidimensional Monge-Kantorovich problem
• The Speed of Mean Glivenko-Cantelli Convergence
• Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness
• I-divergence geometry of probability distributions and minimization problems
• Monge's problem with a quadratic cost by the zero-noise limit of \(h\)-path processes
• From the Schrödinger problem to the Monge-Kantorovich problem
• Minimization of the Kullback information of diffusion processes
• Entropy minimization, \(DAD\) problems, and doubly stochastic kernels
• A large deviation approach to some transportation cost inequalities
• Iterative Bregman Projections for Regularized Transportation Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Monotonicity properties of optimal transportation and the FKG and related inequalities
• Conservative diffusions
• Entropic and Displacement Interpolation: A Computational Approach Using the Hilbert Metric
• Variational processes and stochastic versions of mechanics
• A survey of the Schrödinger problem and some of its connections with optimal transport
• Decomposition of Multivariate Functions
• On the scaling of multidimensional matrices
• The Research Program of Stochastic Deformation (with a View Toward Geometric Mechanics)
• Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations
• Matching for teams
• Estimating Nonnegative Matrices from Marginal Data
• Malliavin calculus and Euclidean quantum mechanics. I: Functional calculus
• Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
• The Least Action Principle and the Related Concept of Generalized Flows for Incompressible Perfect Fluids
• The dual least action problem for an ideal, incompressible fluid
• On pairs of multidimensional matrices
• Computations of optimal transport distance with Fisher information regularization
• Hopf-Cole transformation and Schrödinger problems
• Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
• Fisher information regularization schemes for Wasserstein gradient flows
• Title not available (Why is that?)
• An entropic interpolation proof of the HWI inequality
• Second order differentiation formula on \(\mathsf{RCD}(K,N)\) spaces
• Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport
• Benamou-Brenier and duality formulas for the entropic cost on \(\mathsf{RCD}^*(K,N)\) spaces
• Multi-marginal entropy-transport with repulsive cost
• Multi-marginal Schrödinger bridges
• A Differential Approach to the Multi-Marginal Schrödinger System

Cited In (24)

• Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems
• Cortically based optimal transport
• Quantitative Stability of Regularized Optimal Transport and Convergence of Sinkhorn's Algorithm
• On the Linear Convergence of the Multimarginal Sinkhorn Algorithm
• A non-commutative entropic optimal transport approach to quantum composite systems at positive temperature
• Orlicz space regularization of continuous optimal transport problems
• Time-symmetric optimal stochastic control problems in space-time domains
• Entropical optimal transport, Schrödinger's system and algorithms
• Stochastic Control Liaisons: Richard Sinkhorn Meets Gaspard Monge on a Schrödinger Bridge
• Entropic regularization of Wasserstein distance between infinite-dimensional Gaussian measures and Gaussian processes
• Optimal transportation, modelling and numerical simulation
• Dispersion-constrained martingale Schrödinger problems and the exact joint S\&P 500/VIX smile calibration puzzle
• Unbalanced multi-marginal optimal transport
• Multi-marginal entropy-transport with repulsive cost
• Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
• Stability and sample complexity of divergence regularized optimal transport
• Universal diagonal estimates for minimizers of the Levy-Lieb functional
• Entropy-regularized 2-Wasserstein distance between Gaussian measures
• The dynamical Schrödinger problem in abstract metric spaces
• Displacement smoothness of entropic optimal transport
• Entropic optimal transport: convergence of potentials
• Convergence rate of general entropic optimal transport costs
• The Derivatives of Sinkhorn–Knopp Converge
• Stability of Schrödinger potentials and convergence of Sinkhorn's algorithm

Uses Software

• POT

This page was built for publication: An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2210656)