Gromov-Wasserstein Distances and their Lower Bounds

by Christoph Alexander Weitkamp
Doctoral thesis
Date of Examination:2022-07-07
Date of issue:2022-11-25
Advisor:Prof. Dr. Axel Munk
Referee:Prof. Dr. Axel Munk
Referee:Dr. Katharina Proksch
Persistent Address: http://dx.doi.org/10.53846/goediss-9587

 

 

Files in this item

Name:Thesis_Weitkamp.pdf
Size:16.5Mb
Format:PDF

The following license files are associated with this item:

Abstract

English

In various applications in biochemistry, computer vision and machine learning, it is of great interest to compare general objects in a pose invariant manner. Recently, the following approach has received increased attention: Model the objects considered as metric measure spaces and compare them with the Gromov-Wasserstein distance. While this distance has many theoretically appealing properties and is a natural distance concept in numerous frameworks, it is NP-hard to compute. In consequence, several alternatives to the precise determination of this distance have been proposed. On the one hand, it is possible to approximate local optima of the minimization problem corresponding to the calculation of the Gromov-Wasserstein distance by conditional gradient descent. On the other hand, one can work with efficiently computable surrogates and lower bounds for the previously mentioned distance. This PhD-thesis consists of three research articles that pursue the second approach. More precisely, the first article investigates the statistical potential of a known meaningful lower bound based on distributions of pairwise distances. Its findings are employed for the comparison of 3d-protein structures. The second article proposes a new Gromov-Wasserstein based surrogate specifically tailored for comparing ultrametric measure spaces and explores its theoretical properties. Finally, the third article is concerned with chromatin loop analysis based on average nearest neighbor distance distributions, which are closely related to and in particular stable under the Gromov-Wasserstein distance.
Keywords: Gromov-Wasserstein; Distribution of distances; Ultrametric spaces; Distance-to-Measure signature
 
Statistik