Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26959
Titel: Approximation algorithms for Vietoris-Rips and Čech filtrations
Verfasser: Choudhary, Aruni
Sprache: Englisch
Erscheinungsjahr: 2017
SWD-Schlagwörter: Algorithmus
Geometrie
Topologie
Freie Schlagwörter: Persistent homology
Topological data analysis
Simplicial complexes
Algorithms
Computational topology
Computational geometry
Approximation algorithms
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: 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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-ds-269597
hdl:20.500.11880/26911
http://dx.doi.org/10.22028/D291-26959
Erstgutachter: Mehlhorn, Kurt
Tag der mündlichen Prüfung: 11-Dez-2017
SciDok-Publikation: 14-Dez-2017
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
SE - Max-Planck-Institut für Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
aruni_choudhary_camera_ready_thesis.pdfDissertation7,39 MBAdobe PDFÖffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons