Gaussian entropic optimal transport: Schrödinger bridges and the Sinkhorn algorithm
This work addresses a computational bottleneck in machine learning and generative modeling by enabling exact solutions for Gaussian entropic optimal transport, though it is incremental as it extends existing methods to a specific domain.
The paper tackles the problem of solving entropic optimal transport for Gaussian models, which previously lacked exact finite-dimensional solutions, by introducing a recursive formulation of the Sinkhorn algorithm that relates to Kalman filtering and Riccati equations, enabling practical implementation without approximations and providing closed-form expressions for transport maps and Schrödinger bridges.
Entropic optimal transport problems are regularized versions of optimal transport problems. These models play an increasingly important role in machine learning and generative modelling. For finite spaces, these problems are commonly solved using Sinkhorn algorithm (a.k.a. iterative proportional fitting procedure). However, in more general settings the Sinkhorn iterations are based on nonlinear conditional/conjugate transformations and exact finite-dimensional solutions cannot be computed. This article presents a finite-dimensional recursive formulation of the iterative proportional fitting procedure for general Gaussian multivariate models. As expected, this recursive formulation is closely related to the celebrated Kalman filter and related Riccati matrix difference equations, and it yields algorithms that can be implemented in practical settings without further approximations. We extend this filtering methodology to develop a refined and self-contained convergence analysis of Gaussian Sinkhorn algorithms, including closed form expressions of entropic transport maps and Schrödinger bridges.