Convergence of the Sinkhorn algorithm when the Schrödinger problem has no solution

Baradat, Aymeric; Ventre, Elias

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 33 (2024) no. 5, pp. 1297-1371

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 $\Gamma$-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.

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.

Classification : 65F35, 65B99, 92-08
Keywords: Schrödinger problem, the Sinkhorn algorithm, matrix scaling

[1] Achilles, Eva Implications of convergence rates in Sinkhorn balancing, Linear Algebra Appl., Volume 187 (1993), pp. 109-112 | DOI | Zbl | MR

[2] Benamou, Jean-David; Carlier, Guillaume; Cuturi, Marco; Nenna, Luca; Peyré, Gabriel Iterative Bergman projections for regularized transportation problems, SIAM J. Sci. Comput., Volume 37 (2015) no. 2, p. A1111-A1138 | DOI | Zbl | MR

[3] Braides, Andrea Gamma-convergence for Beginners, Oxford Lecture Series in Mathematics and its Applications, 22, Oxford University Press, 2002 | Zbl | DOI | MR

[4] Brualdi, Richard A. Convex sets of non-negative matrices, Can. J. Math., Volume 20 (1968), pp. 144-157 | DOI | Zbl | MR

[5] Carlier, Guillaume; Duval, Vincent; Peyré, Gabriel; Schmitzer, Bernhard Convergence of entropic schemes for optimal transport and gradient flows, SIAM J. Math. Anal., Volume 49 (2017) no. 2, pp. 1385-1418 | DOI | Zbl | MR

[6] Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier Scaling algorithms for unbalanced optimal transport problems, Math. Comput., Volume 87 (2018) no. 314, pp. 2563-2609 | DOI | Zbl | MR

[7] Csiszár, Imre $I$-divergence geometry of probability distributions and minimization problems, Ann. Probab., Volume 3 (1975), pp. 146-158 | DOI | Zbl | MR

[8] Cuturi, Marco 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] Di Marino, Simone; Gerolin, Augusto 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 | Zbl | MR

[10] Föllmer, Hans 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 | Zbl | DOI

[11] Fortet, Robert Résolution d’un système d’équations de M. Schrödinger, J. Math. Pures Appl., Volume 19 (1940), pp. 83-105 | MR | Zbl | Numdam

[12] Gentil, Ivan; Léonard, Christian; Ripani, Luigia About the analogy between optimal transport and minimal entropy, Ann. Fac. Sci. Toulouse, Math. (6), Volume 26 (2017) no. 3, pp. 569-600 | DOI | MR | Zbl | Numdam

[13] Ghosal, Promit; Nutz, Marcel; Bernton, Espen Stability of entropic optimal transport and Schrödinger bridges, J. Funct. Anal., Volume 283 (2022) no. 9, 109622 | DOI | Zbl | MR

[14] Hagberg, Aric; Swart, Pieter J.; Schult, Daniel A. Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (SciPy 2008) (Varoquaux, Gaël; Millman, Jarrod; Vaught, Travis, eds.), Los Alamos National Laboratory (LANL), Los Alamos, NM (United States) (2008), pp. 11-16 | DOI

[15] Herbach, Ulysse; Bonnaffoux, Arnaud; Espinasse, Thibault; Gandrillon, Olivier Inferring gene regulatory networks from single-cell data: a mechanistic approach, BMC Syst. Biol., Volume 11 (2017), 105 | DOI

[16] Idel, Martin A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps (2016) | arXiv

[17] Kondratyev, Stanislav; Monsaingeon, Léonard; Vorotnikov, Dmitry A new optimal transport distance on the space of finite Radon measures, Adv. Differ. Equ., Volume 21 (2016) no. 11-12, pp. 1117-1164 | Zbl | MR

[18] Lavenant, Hugo; Zhang, Stephen; Kim, Young-Heon; Schiebinger, Geoffrey Towards a mathematical theory of trajectory inference, Ann. Appl. Probab., Volume 34 (2024) no. 1A, pp. 428-500 | DOI | MR

[19] Léonard, Christian From the Schrödinger problem to the Monge–Kantorovich problem, J. Funct. Anal., Volume 262 (2012) no. 4, pp. 1879-1920 | MR | DOI | Zbl

[20] Léonard, Christian 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] Léonard, Christian 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 | Zbl | MR

[22] Liero, Matthias; Mielke, Alexander; Savaré, Giuseppe Optimal entropy-transport problems and a new Hellinger–Kantorovich distance between positive measures, Invent. Math., Volume 211 (2018) no. 3, pp. 969-1117 | DOI | Zbl | MR

[23] Mikami, Toshio Monge’s problem with a quadratic cost by the zero-noise limit of $h$-path processes, Probab. Theory Relat. Fields, Volume 129 (2004) no. 2, pp. 245-260 | DOI | Zbl | MR

[24] Nutz, Marcel Introduction to Entropic Optimal Transport, 2022 (https://www.math.columbia.edu/~mnutz/docs/EOT_lecture_notes.pdf)

[25] Nutz, Marcel; Wiesel, Johannes Entropic optimal transport: convergence of potentials, Probab. Theory Relat. Fields, Volume 184 (2022) no. 1-2, pp. 401-424 | DOI | MR | Zbl

[26] Peyré, Gabriel; Cuturi, Marco Computational Optimal Transport With Applications to Data Science, Found. Trends Mach. Learn., Volume 11 (2019) no. 5-6, pp. 355-607 | DOI | Zbl

[27] Rüschendorf, Ludger Convergence of the iterative proportional fitting procedure, Ann. Stat., Volume 23 (1995) no. 4, pp. 1160-1174 | DOI | MR | Zbl

[28] Rüschendorf, Ludger; Thomsen, Wolfgang Note on the Schrödinger equation and $I$-projections, Stat. Probab. Lett., Volume 17 (1993) no. 5, pp. 369-375 | DOI | MR | Zbl

[29] Sanov, I. N. On the probability of large deviations of random variables (1958) (Technical report)

[30] Santambrogio, Filippo Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, 87, Birkäuser/Springer, 2015 | DOI | Zbl | MR

[31] Schiebinger, Geoffrey; Shu, Jian; Tabaka, Marcin; Cleary, Brian; Subramanian, Vidya; Solomon, Aryeh; Gould, Joshua; Liu, Siyan; Lin, Stacie; Berube, Peter; Lee, Lia; Chen, Jenny; Brumbaugh, Justin; Rigollet, Philippe; Hochedlinger, Konrad; Jaenisch, Rudolf; Regev, Aviv; Lander, Eric S. Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming, Cell, Volume 176 (2019), pp. 928-943 | DOI

[32] Schrödinger, Erwin Über die Umkehrung der Naturgesetze, Sitzungsber. Preuß. Akad. Wiss., Phys.-Math. Kl., Volume 1931 (1931) no. 8-9, pp. 144-153 | Zbl

[33] Schrödinger, Erwin 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 | Zbl | MR | Numdam

[34] Sinkhorn, Richard A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Stat., Volume 35 (1964) no. 2, pp. 876-879 | DOI | Zbl | MR

[35] Sinkhorn, Richard Diagonal equivalence to matrices with prescribed row and column sums, Am. Math. Mon., Volume 74 (1967) no. 4, pp. 402-405 | DOI | Zbl | MR

[36] Soules, George W. The rate of convergence of Sinkhorn balancing, Linear Algebra Appl., Volume 150 (1991), pp. 3-40 | DOI | Zbl | MR

[37] Ventre, Elias 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] Ventre, Elias 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] Ventre, Elias; Herbach, Ulysse; Espinasse, Thibault; Benoit, Gérard; Gandrillon, Olivier One model fits all: combining inference and simulation of gene regulatory networks, PLoS Comput. Biol., Volume 19 (2023) no. 3, e1010962 | DOI

[40] Zambrini, Jean-Claude Variational processes and stochastic versions of mechanics, J. Math. Phys., Volume 27 (1986) no. 9, pp. 2307-2330 | DOI | Zbl | MR