Approximation algorithms for Vietoris-Rips and Čech filtrations

Abstract

Persistent Homology is a tool to analyze and visualize the shape of data from a topological viewpoint. It computes persistence, which summarizes the evolution of topological and geometric information about metric spaces over multiple scales of distances. While computing persistence is quite efficient for low-dimensional topological features, it becomes overwhelmingly expensive for medium to high-dimensional features. In this thesis, we attack this computational problem from several different angles. We present efficient techniques to approximate the persistence of metric spaces. Three of our methods are tailored towards general point clouds in Euclidean spaces. We make use of high dimensional lattice geometry to reduce the cost of the approximations. In particular, we discover several properties of the Permutahedral lattice, whose Voronoi cell is well-known for its combinatorial properties. The last method is suitable for point clouds with low intrinsic dimension, where we exploit the structural properties of the point set to tame the complexity. In some cases, we achieve a reduction in size complexity by trading off the quality of the approximation. Two of our methods work particularly well in conjunction with dimension-reduction techniques: we arrive at the first approximation schemes whose complexities are only polynomial in the size of the point cloud, and independent of the ambient dimension. On the other hand, we provide a lower bound result: we construct a point cloud that requires super-polynomial complexity for a high-quality approximation of the persistence. Together with our approximation schemes, we show that polynomial complexity is achievable for rough approximations, but impossible for sufficiently fine approximations. For some metric spaces, the intrinsic dimension is low in small neighborhoods of the input points, but much higher for large scales of distances. We develop a concept of local intrinsic dimension to capture this property. We also present several applications of this concept, including an approximation method for persistence. This thesis is written in English.

Persistent Homology ist eine Methode zur Analyse und Veranschaulichung von Daten aus topologischer Sicht. Sie berechnet eine topologische Zusammenfassung eines metrischen Raumes, die Persistence genannt wird, indem die topologischen Eigenschaften des Raumes über verschiedene Skalen von Abständen analysiert werden. Die Berechnung von Persistence ist für niederdimensionale topologische Eigenschaften effizient. Leider ist die Berechung für mittlere bis hohe Dimensionen sehr teuer. In dieser Dissertation greifen wir dieses Problem aus vielen verschiedenen Winkeln an. Wir stellen effiziente Techniken vor, um die Persistence für metrische Räume zu approximieren. Drei unserer Methoden eignen sich für Punktwolken im euklidischen Raum. Wir verwenden hochdimensionale Gittergeometrie, um die Kosten unserer Approximationen zu reduzieren. Insbesondere entdecken wir mehrere Eigenschaften des Permutahedral Gitters, dessen Voronoi-Zelle für ihre kombinatorischen Eigenschaften bekannt ist. Die vierte Methode eignet sich für Punktwolken mit geringer intrinsischer Dimension: wir verwenden die strukturellen Eigenschaften, um die Komplexität zu reduzieren. Für einige Methoden zeigen wir einen Trade-off zwischen Komplexität und Approximationsqualität auf. Zwei unserer Methoden funktionieren gut mit Dimensionsreduktionstechniken: wir präsentieren die erste Methode mit polynomieller Komplexität unabhängig von der Dimension. Wir zeigen auch eine untere Schranke. Wir konstruieren eine Punktwolke, für die die Berechnung der Persistence nicht in Polynomzeit möglich ist. Die bedeutet, dass in Polynomzeit nur eine grobe Approximation berechnet werden kann. Für gewisse metrische Räume ist die intrinsiche Dimension gering bei kleinen Skalen aber hoch bei großen Skalen. Wir führen das Konzept lokale intrinsische Dimension ein, um diesen Umstand zu fassen, und zeigen, dass es für eine gute Approximation von Persistenz benutzt werden kann. Diese Dissertation ist in englischer Sprache verfasst.