An Optimal Transport Approach for the Schrödinger Bridge Problem and Convergence of Sinkhorn Algorithm

Simone Di Marino, Augusto Gerolin*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

This paper exploit the equivalence between the Schrödinger Bridge problem (Léonard in J Funct Anal 262:1879–1920, 2012; Nelson in Phys Rev 150:1079, 1966; Schrödinger in Über die umkehrung der naturgesetze. Verlag Akademie der wissenschaften in kommission bei Walter de Gruyter u, Company, 1931) and the entropy penalized optimal transport (Cuturi in: Advances in neural information processing systems, pp 2292–2300, 2013; Galichon and Salanié in: Matching with trade-offs: revealed preferences over competing characteristics. CEPR discussion paper no. DP7858, 2010) 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ödinger system. Our method extends also when we have more than two marginals: the main new result is the proof that the Sinkhorn algorithm converges even in the continuous multi-marginal case. This provides also an alternative proof of the convergence of the Sinkhorn algorithm in two marginals.

Original languageEnglish
Article number27
Pages (from-to)1-28
Number of pages28
JournalJournal of Scientific Computing
Volume85
Issue number2
Early online date19 Oct 2020
DOIs
Publication statusPublished - 1 Nov 2020

Keywords

  • Entropic regularization of optimal transport
  • Iterative proportional fitting procedure
  • Kantorovich duality
  • Schrödinger problem
  • Sinkhorn algorithm

Fingerprint

Dive into the research topics of 'An Optimal Transport Approach for the Schrödinger Bridge Problem and Convergence of Sinkhorn Algorithm'. Together they form a unique fingerprint.

Cite this