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

Funding

S. D. M. is member of Gruppo Nazionale per l’Analisi Matematica, la Probabilità e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM). A.G. acknowledges the European Research Council under H2020/MSCA-IF“OTmeetsDFT” [Grant ID: 795942]. This work started when the second author visited the first author, while he was working at the Scuola Normale Superiore di Pisa (INdAM unit). The authors wants to thank G. Carlier, C. Léonard and L. Tamanini for useful discussions. S. D. M. is member of Gruppo Nazionale per l?Analisi Matematica, la Probabilit? e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM). A.G. acknowledges the European Research Council under H2020/MSCA-IF?OTmeetsDFT? [Grant ID: 795942]. This work started when the second author visited the first author, while he was working at the Scuola Normale Superiore di Pisa (INdAM unit). The authors wants to thank G. Carlier, C. L?onard and L. Tamanini for useful discussions.

FundersFunder number
GNAMPA
Istituto Nazionale di Alta Matematica "Francesco Severi"
Horizon 2020 Framework Programme795942
European Research Council

    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