Loading…
Optimal transport: theory, algorithms and applications
Lindheim, Johannes von
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.
Optimaler Transport (OT), der sich mit dem Matching von Wahrscheinlichkeits- oder positiven Maßen beschäftigt, wurde von Monge im Jahr 1781 eingeführt [109]. Insbesondere die Relaxierung mit linearer Programmierung von Kantorovich 1942 [93] und die Einführung von entropischer Regularisierung in OT von Leonard [101] und Cuturi [60] vor etwa einem Jahrzehnt hatten großen Einfluss auf OT, sowohl in Bezug auf Beiträge zu seiner Theorie, als auch in Bezug auf seine Rolle als häufig verwendetes Werkzeug in vielen Anwendungen in Data Science und maschinellem Lernen, Bildverarbeitung, Biologie, Sozialwissenschaften, Wirtschaftswissenschaften und Finanzmathematik. Bis heute ist OT ein lebendiges Forschungsfeld mit ständig neuen Begriffen und Varianten, Erkenntnissen, Algorithmen und Anwendungen.
Dies ist eine kumulative Dissertation, die die Publikationen [96, 153, 24, 152, 151] und die unveröffentlichte Arbeit [154] im Anhang A enthält. Wir beginnen mit einer Übersicht über unsere zugehörigen Erkenntnisse und Ergebnisse.
Zunächst geben wir in Kapitel 1 eine kurze Einführung in OT, mit besonderem Augenmerk auf die Konzepte, die mit den Beiträgen in dieser Arbeit verbunden sind.
In Kapitel 2, das [24] im Anhang A.1 entspricht, kombinieren wir die Begriffe des multimarginalen OT für das Matching von mehr als zwei Maßen und des unbalacierten OT, der in Anwendungen oft vorzuziehen ist, da er kein exaktes Matching der gegebenen Maße erfordert. Genauer führen wir das unbalancierte, multi-marginale optimale Transportproblem (UMOT) und sein duales Problem ein und zeigen, dass es einen eindeutigen optimalen Transportplan gibt. Wir geben einen entsprechenden Sinkhorn-ähnlichen Algorithmus und beweisen dessen Konvergenz unter milden Regularitätsannahmen an die Penalisierungsterme der marginalen Maße. Für Kostenfunktionen, die gemäß einem Baum strukturiert sind, können die Iterierten effizient berechnet werden. Am Ende zeigen wir die Vorteile unseres Frameworks in zwei Anwendungen im Vergleich zu einer paarweise gekoppelten Formulierung. Zuerst zeigen wir theoretisch und numerisch, dass bei regularisierten Baryzenter-Problemen die UMOT-Lösungen weniger unscharf sind. Außerdem zeigt UMOT in einem Transferoperator-Ansatz für die Entrauschung einer Zeitreihe von Maßen numerisch bessere Lösungen.
In Kapitel 3 fassen wir die Arbeiten [152] und [151] zusammen, die dem Anhang A.3 bzw. A.4 entsprechen, sowie die unveröffentlichte Arbeit [154] im Anhang A.5. Zunächst betrachten wir in Abschnitt 3.1 das Problem der Berechnung von Wasserstein-Baryzentren von diskreten Maßen, das im Allgemeinen NP-schwer ist. Hier analysieren wir ein bekanntes einfaches Verfahren zur Approximation von Wasserstein-p-Baryzentren, wobei wir hauptsächlich den populärsten Fall p = 2 und p = 1 betrachten, der weniger häufig diskutiert wird. Dieses Framework benötigt lediglich die Lösungen von N −1 oder N(N −1)/2 v Standard-OT-Berechnungen zwischen Paaren den N gegebenen Maße und erzeugt dünn besetzte Lösungen. Es zeigt vielversprechende numerische Ergebnisse im free-support-Setting im numerischen Vergleich zu anderen Algorithmen aus der Literatur. Wir zeigen, dass der relative Fehler höchstens N bzw. 2 sein kann f¨ur p = 1, 2, was nahezu scharf ist.
Diese Fehlerschranken erweisen sich in der Regel als drastisch niedriger für ein bestimmtes, gegebenes Problem und garantieren in unseren numerischen Experimenten Fehler von höchstens ein paar Prozent. Wir übertragen diese Algorithmen auf das entsprechende multi-marginale Setting und schlagen einen weiteren Greedy-Algorithmus vor, für den wir auch eine theoretische Analyse der Approximationsqualität anstellen. Schließlich zeigen wir in Abschnitt 3.2 mehrere Beziehungen auf zwischen einem Algorithmus namens generalized iterative scaling (GIS) bzw. simultaneous multiplicative algebraic reconstruction technique (SMART) und regularisiertem OT mit affinen Nebenbedingungen. Wir geben einen neuen Beweis für die Konvergenz einer block-iterativen Version dieses Algorithmus, die gut in das OT-Setting passt. Außerdem zeigen wir, dass dieser Algorithmus auf mehrere interessante OT-Probleme zugeschnitten werden kann. Erstens finden wir das Maß, das unter Nebenbedingungen an seine Momente die regularisierte OT-Divergenz zu einem gegebenen Maß minimiert. Zweitens und drittens liefert das vorgeschlagene Framework einen Algorithmus zur Lösung eines regularisierten martingale-OT-Problems sowie einer relaxierten Version eines Problems namens barcentric weak OT.
In Kapitel 4 geht es um OT in Anwendungen. Wir fassen die Beiträge von [96] in Appendix A.2 und [153] in Appendix A.6 zusammen. Diese Beiträge liegen nicht im OT selbst, sondern in einem Ansatz, der es als Werkzeug nutzt. Erstens schlagen wir in Abschnitt 4.1 vor, regularisierten OT für die Konstruktion von Transferoperatoren zu verwenden, die wir zur Detektion kohärenter Mengen für ein gegebenes Paar von Maßen nutzen. Dies kann als eine temporale Form des spektralen Clustering angesehen werden. Wir zeigen, dass die entropische Regularisierung gut zu den notwendigen Anforderungen an die Robustheit der kohärenten Mengen gegen statistisches Rauschen passt. Darüber hinaus kann sie als optimaler Weg interpretiert werden, um die vollständige Dynamik zu erhalten unter den sehr eingeschränkten Informationen einer anfänglichen und einer endgültigen Partikelverteilung, unter der Annahme, dass sich die Partikel gemäß einer Brownschen Bewegung verhalten. Im nächsten Abschnitt 4.2 verwenden wir OT als Maß für die Persistenz von Wetterfronten, mit dem wir sogenannte synoptische und lokale Fronten klassifizieren. In Abschnitt 4.3 geben wir schließlich einen einheitlichen Zugang zu vielen Phänomenen und Methoden, die als “persistent structures” bezeichnet werden und die auf die Charakterisierung, Identifizierung oder das Tracking von atmosphärischen Strukturen abzielen, und zeigen auf, wie diese mit den beiden zuvor genannten Anwendungen zusammenhängen.
Abschließende Bemerkungen finden sich in Kapitel 5, in dem wir verschiedene mögliche Wege für zukünftige Forschung aufzeigen. Besonderes Augenmerk wurde bei allen Beiträgen dieser Arbeit auf die Einfachheit und Effizienz der Algorithmen gelegt. Der Sinkhorn-Algorithmus, spektrales Clustering und der GIS/SMART-Algorithmus sind einige prominente Beispiele für solche Algorithmen im Zusammenhang mit Themen dieser Arbeit, die die Bedeutung der Einfachheit für einen Einfluss auf die Forschung zeigen.
