Optimal transport: theory, algorithms and applications

Optimal transport (OT), which deals with the matching of probability or positive measures, has been originally introduced by Monge in 1781. In particular its linear programming relaxation of Kantorovich in 1942 and the introduction of entropic regularization to OT by Léonard and Cuturi around a decade ago have attracted lots of attention, both regarding contributions to its theory, but also as a frequently used tool in many applications in data science and machine learning, image processing, biology, social sciences, economics and mathematical finance. Up to now, OT is a vivid field of research with constantly appearing new variants, insights, algorithms and applications. This is a cumulative thesis, which contains the publications [96, 153, 24, 152, 151] and the unpublished work [154] in the Appendix A. We start with an overview of our corresponding findings and results. First, in Chapter 1, we give a brief introduction to OT, with a particular focus on the concepts connected to the contributions in this thesis. Next, in Chapter 2, which corresponds to [24] in the Appendix A.1, we combine the notions multi-marginal OT for matching more than two measures, and unbalanced OT, which is often preferable in applications, since it does not require an exact matching of the given measures. More precisely, we introduce the unbalanced multi-marginal optimal transport problem (UMOT) and its dual, and show that a unique optimal transport plan exists. We provide a corresponding Sinkhorn-like algorithm prove its convergence under mild regularity assumptions on the marginal penalization terms. For cost functions decoupling according to a tree, the iterates can be computed efficiently. At the end, we show the advantages of our framework in two applications in comparison to a pairwise coupled formulation. Firstly, we show theoretically and numerically that for regularized barycenter problems, the solutions corresponding to UMOT are less blurred. Secondly, UMOT performs better numerically in a transfer operator approach for the denoising of a time series of measures. In Chapter 3, we summarize the papers [152] and [151] corresponding to Appendix A.3 and A.4, respectively, as well as the unpublished work [154] in Appendix A.5. First, in Section 3.1, we consider the problem of computing Wasserstein barycenters of discrete measures, which is NP-hard in general. Here, we analyze a well-known simple framework for approximating Wasserstein-p barycenters, where we mainly consider the most common case p=2 and p=1, which is not as well discussed. The framework requires only the solutions of N-1 or N(N-1)/2 standard two-marginal OT computations between the $N$ input measures, respectively, and produces sparse support solutions. Furthermore, it shows good numerical results in comparison to other algorithms from the literature. We show that the worst-case relative error is at most N and 2, respectively, for both p=1, 2, which is practically sharp. These error bounds usually turn out to be drastically lower in for a given particular problem, guaranteeing errors of at most a few percent in our numerical experiments. We proceed to transfer these algorithms to the corresponding multi-marginal setting and propose another greedy algorithm, for which we also provide a theoretical analysis regarding approximation quality. Next, in Section 3.2, we reveal several relations between the generalized iterative scaling algorithm (GIS) or simultaneous multiplicative algebraic reconstruction technique (SMART) and regularized OT with affine constraints. We give a new proof for the convergence of a block-iterative version of this algorithm, which fits well to the OT setting. Moreover, we show that this algorithm can be tailored to several interesting OT problems. First, we find the measure that minimizes the regularized OT divergence to a given measure under moment constraints. Second and third, the proposed framework yields an algorithm for solving a regularized martingale OT problem, as well as a relaxed version of the barycentric weak OT problem. Chapter 4 is about OT in applications. We summarize the contributions from [96] in Appendix A.2 and [153] in Appendix A.6. These contributions do not lie within OT itself, but in an approach using it as a tool. First, in Section 4.1, we propose to use regularized OT for the construction of transfer operators, which we use to detect coherent sets for a given pair of measures. This can be seen as a temporal form of spectral clustering. We show that entropic regularization fits well with the necessary noise-robustness requirement of coherence. Moreover, it can be interpreted as an optimal way of retrieving the full dynamics given the very restricted information of an initial and a final particle distribution moving under the assumption of Brownian motion. Next, in Section 4.2, we use OT as a measure of persistence for weather fronts, which we use to distinguish between so-called synoptical and local fronts. Finally, in Section 4.3, we give a unified abstraction of many phenomena and methods called "persistent structures" that target the characterization, identification or tracking of atmospheric structures, and how it relates to the two formerly mentioned applications. Concluding remarks are given in Chapter 5, where we show different possible avenues for future research. Special attention throughout the contributions in this thesis has been paid to the simplicity and efficiency of the algorithms. The Sinkhorn algorithm, spectral clustering and the GIS/SMART algorithm are a few prominent examples for such algorithms related to topics in this thesis that showcase the major importance of simplicity for their impact on research.

Author dc:creator

• Lindheim, Johannes von

Advisor dc:contributor.advisor

• Steidl, Gabriele

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Identifier URI

https://doi.org/10.14279/depositonce-18201

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/19405