Abstract: Optimal transport is a classical problem in mathematics, and the topic has seen rapid development over the last decades. In particular, there has recently been a surge of research related to applications of optimal transport in a number of different areas, as well as computational methods for numerically solving the problem. Today, the most well-known algorithm for solving the problem is arguably Sinkhorn’s method, also known by names such as the Sinkhorn-Knopp algorithm, the matrix balancing algorithm, the matrix scaling algorithm, iterative proportional fitting, and others.
In this talk, I will give a short introduction to optimal transport and to Sinkhorn’s method. I will also illustrate how different problems in, e.g., imaging, information fusion, and density optimal control can be formulated in the framework. Moreover, the underlying structure in some of these problems, such as barycenter problems, displacement interpolation problems, and multi-species density control problems, have led us to consider a generalization of the classical optimal transport problem, namely graph-structured multi-marginal optimal transport. In this talk, I will introduce this class of problems and show how Sinkhorn’s method can be extended to this problem class. However, in the multi-marginal setting, Sinkhorn’s method only partially alleviates the computational difficulty. This is because computing the corresponding projections needed in the method in a naïve fashion scales exponentially in the number of marginals. Nevertheless, I will present methods for how these projections can be efficiently compute when the underlying graph structure is, in some sense, simple. In particular, I will show how the projections can be computed in the case when the graph is a tree.
