Schödinger Bridges in Optimal Transport

Abstract

This thesis examines the connection between the Optimal Transport (OT) and the Schrödinger Bridge (SB) problem. Both analytical and numerical approaches to finding the optimal solution are discussed.

Originating from an engineering perspective, Optimal Transport seeks to find the minimal cost of transporting mass from one distribution to another. In the reformulation to the SB problem, these distributions are considered probability densities, and the solution can best be described as the most likely transition from the initial density to the other, expressed as a probability law. The optimal probability law is found by minimizing its Kullback-Leibler (KL) divergence when compared to a prior.

The theoretical mathematical foundations of the OT and SB problems are first explained. Here, the OT problem is approximated with an entropy regularisation term, which links it directly to the SB problem, by means of the KL-divergence.
To derive the optimal solution of the SB problem, its similarity with the discrete entropic OT problem is discussed. The existence of the unique solution to the discrete problem is found by its strict convexity. With the Lagrangian, the form of the solution it is established. In the continuous case, an iterative scheme to finding the solution is developed using similar computations. Scaling functions that define the unique optimal probability are obtained.
For one-dimensional Gaussian marginals, analytical update schemes are derived. First this is done for marginals with zero mean. For the Gaussians with non-zero mean, a more complicated derivation is explained, that considers the shifts in the mean.
Python implementations, found in appendices C, D, E and on GitHub 1, are made for all three update schemes, using numerical integration. The performance of the algorithms is compared, and their results show to be extremely similar. The general algorithm converges faster, but also takes more numerical approximations.
From the newly made computational general algorithm, an extension is derived that visualises intermediate marginals over a time grid, creating the "bridge". This is done for both Gaussian and non-Gaussian marginals. It can here be seen that generally, the algorithm performs better when marginals are "standard" Gaussian.
All in all, the Schrödinger Bridge provides a useful algorithm that can be used to solve potentially complicated OT problems. Both numerical implementations as analytical approaches give useful tools for finding solutions effectively. Additionally, bridge visualisations can be made neatly for a broad range of marginals.
Throughout the process of writing this thesis, the AI programme ChatGPTwas consulted for suggestions on academic sources with supporting arguments. Furthermore, it has been implemented to check for small errors in Python code as well as spelling, grammar and idiom mistakes, whilst maintaining the human-written text.