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

Simone Di Marino; Augusto Gerolin

doi:10.1007/s10915-020-01325-7

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

AIMMS

Research output: Contribution to Journal › Article › Academic › peer-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 language	English
Article number	27
Pages (from-to)	1-28
Number of pages	28
Journal	Journal of Scientific Computing
Volume	85
Issue number	2
Early online date	19 Oct 2020
DOIs	https://doi.org/10.1007/s10915-020-01325-7
Publication status	Published - 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.

Funders	Funder number
GNAMPA
Istituto Nazionale di Alta Matematica "Francesco Severi"
Horizon 2020 Framework Programme	795942
European Research Council

Keywords

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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/s10915-020-01325-7

Persistent URL (handle)

Persistent link

Cite this

@article{808ca7f554884ca496c70865daf35637,

title = "An Optimal Transport Approach for the Schr{\"o}dinger Bridge Problem and Convergence of Sinkhorn Algorithm",

abstract = "This paper exploit the equivalence between the Schr{\"o}dinger Bridge problem (L{\'e}onard in J Funct Anal 262:1879–1920, 2012; Nelson in Phys Rev 150:1079, 1966; Schr{\"o}dinger in {\"U}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{\'e} 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{\"o}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.",

keywords = "Entropic regularization of optimal transport, Iterative proportional fitting procedure, Kantorovich duality, Schr{\"o}dinger problem, Sinkhorn algorithm",

author = "Marino, {Simone Di} and Augusto Gerolin",

year = "2020",

month = nov,

day = "1",

doi = "10.1007/s10915-020-01325-7",

language = "English",

volume = "85",

pages = "1--28",

journal = "Journal of Scientific Computing",

issn = "0885-7474",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

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

AU - Marino, Simone Di

AU - Gerolin, Augusto

PY - 2020/11/1

Y1 - 2020/11/1

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

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

KW - Entropic regularization of optimal transport

KW - Iterative proportional fitting procedure

KW - Kantorovich duality

KW - Schrödinger problem

KW - Sinkhorn algorithm

UR - http://www.scopus.com/inward/record.url?scp=85092762857&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85092762857&partnerID=8YFLogxK

U2 - 10.1007/s10915-020-01325-7

DO - 10.1007/s10915-020-01325-7

M3 - Article

AN - SCOPUS:85092762857

SN - 0885-7474

VL - 85

SP - 1

EP - 28

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

IS - 2

M1 - 27

ER -

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

Abstract

Funding

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this