The Sinkhorn algorithm is the most popular method for solving the entropy minimization problem called the Schr\"odinger problem: in the non-degenerate cases, the latter admits a unique solution towards which the algorithm converges linearly. Here, motivated by recent applications of the Schr\"odinger problem with respect to structured stochastic processes (such as increasing ones), we study the Sinkhorn algorithm in degenerate cases where it might happen that no solution exist at all. We show that in this case, the algorithm ultimately alternates between two limit points. Moreover, these limit points can be used to compute the solution of a relaxed version of the Schr\"odinger problem, which appears as the $\Gamma$-limit of a problem where the marginal constraints are replaced by asymptotically large marginal penalizations, exactly in the spirit of the so-called unbalanced optimal transport. Finally, our work focuses on the support of the solution of the relaxed problem, giving its typical shape and designing a procedure to compute it quickly. We showcase promising numerical applications related to a model used in cell biology.
翻译:辛克霍恩算法是解决最小化问题最受欢迎的方法,叫做Schr\'odinger问题:在非脱产案例中,后者承认一种独特的解决办法,使算法线性地趋于一致。在这里,由于施尔\'odinger问题的最近应用,我们在结构性随机化过程(如增加的)方面研究了Sinkhorn算法,在可能根本不存在解决办法的堕落案例中,对Sinkhorn算法进行了研究。我们表明,在这种情况下,算法最终在两个限制点之间交替使用。此外,这些限制点可用于计算舒尔”odinger问题的宽松版本的解决方法,这似乎是一个边际限制被无序大规模边际惩罚取代的问题的$\Gamma$-限制值。我们完全本着所谓的不平衡最佳运输精神,我们的工作侧重于支持缓和问题的解决办法,赋予其典型的形状,并设计一个快速的计算程序。我们展示了与细胞生物学中使用的模型有关的有希望的数字应用。</s>