Stochastic control liaisons: Richard Sinkhorn meets Gaspard Monge on a Schroedinger bridge
arXiv:2005.10963
Abstract
In 1931/32, Schroedinger studied a hot gas Gedankenexperiment, an instance of large deviations of the empirical distribution and an early example of the so-called maximum entropy inference method. This so-called Schroedinger bridge problem (SBP) was recently recognized as a regularization of the Monge-Kantorovich Optimal Mass Transport (OMT), leading to effective computation of the latter. Specifically, OMT with quadratic cost may be viewed as a zero-temperature limit of SBP, which amounts to minimization of the Helmholtz's free energy over probability distributions constrained to possess given marginals. The problem features a delicate compromise, mediated by a temperature parameter, between minimizing the internal energy and maximizing the entropy. These concepts are central to a rapidly expanding area of modern science dealing with the so-called {\em Sinkhorn algorithm} which appears as a special case of an algorithm first studied by the French analyst Robert Fortet in 1938/40 specifically for Schroedinger bridges. Due to the constraint on end-point distributions, dynamic programming is not a suitable tool to attack these problems. Instead, Fortet's iterative algorithm and its discrete counterpart, the Sinkhorn iteration, permit computation by iteratively solving the so-called {\em Schroedinger system}. In both the continuous as well as the discrete-time and space settings, {\em stochastic control} provides a reformulation and dynamic versions of these problems. The formalism behind these control problems have attracted attention as they lead to a variety of new applications in spacecraft guidance, control of robot or biological swarms, sensing, active cooling, network routing as well as in computer and data science. This multifacet and versatile framework, intertwining SBP and OMT, provides the substrate for a historical and technical overview of the field taken up in this paper.
arXiv comment67 pages
References in corpus (15)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Relative Entropy: Free Energy Associated with Equilibrium Fluctuations and Nonequilibrium Deviations
- Entropy Production of Brownian Macromolecules with Inertia
- Centrality measures and thermodynamic formalism for complex networks
- Feedback cooling of the normal modes of a massive electromechanical system to submillikelvin temperature
- Scaling Algorithms for Unbalanced Transport Problems
- Hilbert's projective metric in quantum information theory
- Hypoelliptic diffusion and human vision: a semi-discrete new twist
- Entropic regularization of continuous optimal transport problems
- On the form of the large deviation rate function for the empirical measures of weakly interacting systems
- Continuous-Flow Graph Transportation Distances
- Schrödinger Bridge Samplers
- Stochastic control, entropic interpolation and gradient flows on Wasserstein product spaces
- Revisiting Fortet's proof of existence of a solution to the Schrödinger system
- Alleviating Label Switching with Optimal Transport