L’algorithme de Sinkhorn est une méthode largement utilisée pour calculer les solutions du problème de Schrödinger car il converge dès que ce dernier admet une solution, et à un taux linéaire dès que cette solution a le même support que la matrice de référence. Récemment, il a été proposé d’appliquer cette théorie à des situations biologiques modélisées par des processus stochastiques structurés donnant lieu à des problèmes de Schrödinger dégénérés pouvant ne pas avoir de solution. Dans cet article, nous démontrons qu’en l’absence de solution, l’algorithme de Sinkhorn admet deux valeurs d’adhérence qui permettent de calculer la solution d’un problème relaxé où les contraintes marginales du problème de Schrödinger sont remplacées par une pénalisation, dans la limite ou celle-ci tend vers l’infini. Notre analyse nous permet également de caractériser le support de la solution, à la fois dans le problème original et dans sa version relaxée. Enfin, nous présentons des applications numériques prometteuses pour l’étude d’un problème de biologie cellulaire.
The Sinkhorn algorithm is one of the most popular methods for solving the Schrödinger problem: it is known to converge as soon as the latter has a solution, and with a linear rate when the solution has the same support as the reference coupling. Motivated by recent applications of the Schrödinger problem where structured stochastic processes lead to degenerate situations with possibly no solution, we show that the Sinkhorn algorithm still gives rise in this case to exactly two limit points, that can be used to compute the solution of a relaxed version of the Schrödinger problem, which appears as the -limit of a problem where the marginal constraints are replaced by marginal penalizations. These results also allow to develop a theoretical procedure for characterizing the support of the solution – both in the original and in the relaxed problem – for any reference coupling and marginal constraints. We showcase promising numerical applications related to a model used in cell biology.
Accepté le :
Publié le :
Mots-clés : Schrödinger problem, the Sinkhorn algorithm, matrix scaling
Aymeric Baradat 1 ; Elias Ventre 2
CC-BY 4.0
@article{AFST_2024_6_33_5_1297_0,
author = {Aymeric Baradat and Elias Ventre},
title = {Convergence of the {Sinkhorn} algorithm when the {Schr\"odinger} problem has no solution},
journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
pages = {1297--1371},
publisher = {Universit\'e Paul Sabatier, Toulouse},
volume = {Ser. 6, 33},
number = {5},
year = {2024},
doi = {10.5802/afst.1800},
language = {en},
url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1800/}
}
TY - JOUR AU - Aymeric Baradat AU - Elias Ventre TI - Convergence of the Sinkhorn algorithm when the Schrödinger problem has no solution JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2024 SP - 1297 EP - 1371 VL - 33 IS - 5 PB - Université Paul Sabatier, Toulouse UR - https://afst.centre-mersenne.org/articles/10.5802/afst.1800/ DO - 10.5802/afst.1800 LA - en ID - AFST_2024_6_33_5_1297_0 ER -
%0 Journal Article %A Aymeric Baradat %A Elias Ventre %T Convergence of the Sinkhorn algorithm when the Schrödinger problem has no solution %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2024 %P 1297-1371 %V 33 %N 5 %I Université Paul Sabatier, Toulouse %U https://afst.centre-mersenne.org/articles/10.5802/afst.1800/ %R 10.5802/afst.1800 %G en %F AFST_2024_6_33_5_1297_0
Aymeric Baradat; Elias Ventre. Convergence of the Sinkhorn algorithm when the Schrödinger problem has no solution. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 33 (2024) no. 5, pp. 1297-1371. doi : 10.5802/afst.1800. https://afst.centre-mersenne.org/articles/10.5802/afst.1800/
[1] Implications of convergence rates in Sinkhorn balancing, Linear Algebra Appl., Volume 187 (1993), pp. 109-112 | DOI | MR | Zbl
[2] Iterative Bergman projections for regularized transportation problems, SIAM J. Sci. Comput., Volume 37 (2015) no. 2, p. A1111-A1138 | DOI | MR | Zbl
[3] Gamma-convergence for Beginners, Oxford Lecture Series in Mathematics and its Applications, 22, Oxford University Press, 2002 | DOI | MR | Zbl
[4] Convex sets of non-negative matrices, Can. J. Math., Volume 20 (1968), pp. 144-157 | DOI | MR | Zbl
[5] Convergence of entropic schemes for optimal transport and gradient flows, SIAM J. Math. Anal., Volume 49 (2017) no. 2, pp. 1385-1418 | DOI | MR | Zbl
[6] Scaling algorithms for unbalanced optimal transport problems, Math. Comput., Volume 87 (2018) no. 314, pp. 2563-2609 | DOI | MR | Zbl
[7] -divergence geometry of probability distributions and minimization problems, Ann. Probab., Volume 3 (1975), pp. 146-158 | DOI | MR | Zbl
[8] Sinkhorn distances: Lightspeed computation of optimal transport, NIPS’13: Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2 (Advances in Neural Information Processing Systems), Volume 26, Curran Associates, Inc. (2013), pp. 2292-2300
[9] An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm, J. Sci. Comput., Volume 85 (2020) no. 2, 27 | DOI | MR | Zbl
[10] Random fields and diffusion processes, École d’Été de Probabilités de Saint-Flour XV-XVII, 1985-87 (Lecture Notes in Mathematics), Volume 1362, Springer, 1988, pp. 101-203 | DOI | Zbl
[11] Résolution d’un système d’équations de M. Schrödinger, J. Math. Pures Appl., Volume 19 (1940), pp. 83-105 | Numdam | MR | Zbl
[12] About the analogy between optimal transport and minimal entropy, Ann. Fac. Sci. Toulouse, Math. (6), Volume 26 (2017) no. 3, pp. 569-600 | DOI | Numdam | MR | Zbl
[13] Stability of entropic optimal transport and Schrödinger bridges, J. Funct. Anal., Volume 283 (2022) no. 9, 109622 | DOI | MR | Zbl
[14] Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (SciPy 2008) (Gaël Varoquaux; Jarrod Millman; Travis Vaught, eds.), Los Alamos National Laboratory (LANL), Los Alamos, NM (United States) (2008), pp. 11-16 | DOI
[15] Inferring gene regulatory networks from single-cell data: a mechanistic approach, BMC Syst. Biol., Volume 11 (2017), 105 | DOI
[16] A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps (2016) | arXiv
[17] A new optimal transport distance on the space of finite Radon measures, Adv. Differ. Equ., Volume 21 (2016) no. 11-12, pp. 1117-1164 | MR | Zbl
[18] Towards a mathematical theory of trajectory inference, Ann. Appl. Probab., Volume 34 (2024) no. 1A, pp. 428-500 | DOI | MR
[19] From the Schrödinger problem to the Monge–Kantorovich problem, J. Funct. Anal., Volume 262 (2012) no. 4, pp. 1879-1920 | DOI | MR | Zbl
[20] Some properties of path measures, Séminaire de Probabilités XLVI (Lecture Notes in Mathematics), Volume 2123, Springer, 2014, pp. 207-230 | DOI | Zbl
[21] A survey of the Schrödinger problem and some of its connections with optimal transport, Discrete Contin. Dyn. Syst., Ser. A, Volume 34 (2014) no. 4, pp. 1533-1574 | DOI | MR | Zbl
[22] Optimal entropy-transport problems and a new Hellinger–Kantorovich distance between positive measures, Invent. Math., Volume 211 (2018) no. 3, pp. 969-1117 | DOI | MR | Zbl
[23] Monge’s problem with a quadratic cost by the zero-noise limit of -path processes, Probab. Theory Relat. Fields, Volume 129 (2004) no. 2, pp. 245-260 | DOI | MR | Zbl
[24] Introduction to Entropic Optimal Transport, 2022 (https://www.math.columbia.edu/~mnutz/docs/EOT_lecture_notes.pdf)
[25] Entropic optimal transport: convergence of potentials, Probab. Theory Relat. Fields, Volume 184 (2022) no. 1-2, pp. 401-424 | DOI | MR | Zbl
[26] Computational Optimal Transport With Applications to Data Science, Found. Trends Mach. Learn., Volume 11 (2019) no. 5-6, pp. 355-607 | DOI | Zbl
[27] Convergence of the iterative proportional fitting procedure, Ann. Stat., Volume 23 (1995) no. 4, pp. 1160-1174 | DOI | MR | Zbl
[28] Note on the Schrödinger equation and -projections, Stat. Probab. Lett., Volume 17 (1993) no. 5, pp. 369-375 | DOI | MR | Zbl
[29] On the probability of large deviations of random variables (1958) (Technical report)
[30] Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, 87, Birkäuser/Springer, 2015 | DOI | MR | Zbl
[31] Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming, Cell, Volume 176 (2019), pp. 928-943 | DOI
[32] Über die Umkehrung der Naturgesetze, Sitzungsber. Preuß. Akad. Wiss., Phys.-Math. Kl., Volume 1931 (1931) no. 8-9, pp. 144-153 | Zbl
[33] Sur la théorie relativiste de l’électron et l’interprétation de la mécanique quantique, Ann. Inst. Henri Poincaré, Volume 2 (1932) no. 4, pp. 269-310 | Numdam | MR | Zbl
[34] A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Stat., Volume 35 (1964) no. 2, pp. 876-879 | DOI | MR | Zbl
[35] Diagonal equivalence to matrices with prescribed row and column sums, Am. Math. Mon., Volume 74 (1967) no. 4, pp. 402-405 | DOI | MR | Zbl
[36] The rate of convergence of Sinkhorn balancing, Linear Algebra Appl., Volume 150 (1991), pp. 3-40 | DOI | MR | Zbl
[37] Reverse engineering of a mechanistic model of gene expression using metastability and temporal dynamics, In Silico Biol., Volume 14 (2021) no. 3–4, pp. 89-113 | DOI
[38] Analyse, calibration et évaluation de modèles stochastiques d’expression des gènes, Ph. D. Thesis, École Normale Supérieure de Lyon, France (2022) (https://inserm.hal.science/INSA-LYON-THESES/tel-03848137v1)
[39] One model fits all: combining inference and simulation of gene regulatory networks, PLoS Comput. Biol., Volume 19 (2023) no. 3, e1010962 | DOI
[40] Variational processes and stochastic versions of mechanics, J. Math. Phys., Volume 27 (1986) no. 9, pp. 2307-2330 | DOI | MR | Zbl
Cité par Sources :