Računanje enodimenzionalne vztrajne homologije v geodezični metriki : magistrsko delo

Čufar, Matija (author), Virk, Žiga (mentor)

V nalogi je predstavljen algoritem za računanje enodimenzionalne vztrajne homologije v geodezični metriki. Uporaba geodezične metrike nam omogoča, da iz točkastih podatkov ocenimo najkrajšo bazo prve homološke grupe prostora iz katerega smo točke vzorčili. V nalogi najprej predstavimo teoretično ozadje enodimenzionalne vztrajne homologije na geodezičnih prostorih. Izkaže se, da so kritične vrednosti vztrajne homologije povezane s sklenjenimi geodetkami, ki predstavljajo najkrajšo bazo prve homološke grupe geodezičnega prostora. V drugem delu naloge z uporabe predstavljene teorije predstavimo lasten algoritem in ga analiziramo. Na koncu predstavimo še rezultate, ki smo jih dobimi z implementacijo algoritma v programskem jeziku Julia. Za izdelavo rezultatov smo uporabili nekaj sintetičnih množic podatkov in eno, večjo, množico podatkov iz realnega sveta.

• Language: Slovenian
• Keywords: Računska topologija, topološka analiza podatkov, algoritmi, homologija, vztrajna homologija.
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics; FRI - Faculty of Computer and Information Science
• Year: 2020
• PID: 20.500.12556/RUL-114071
• UDC: 515.1
• COBISS.SI-ID: 18913881
• Publication date in RUL: 12.02.2020

Secondary language

• Language: English
• Title: Computing one-dimensional persistent homology in a geodesic metric

Abstract

In this thesis, we present an algorithm that computes the one-dimensional persistent homology in a geodesic metric. The use of a geodesic metric allows us to approximate the shortest homology basis of the underlying space. First, we present the theoretical background of one-dimensional persistent homology of geodesic spaces. The main result of this section is the connection between the critical points of persistent homology and geodesic loops in the space, which form the shortest basis of the first homology group. Next, we present a new algorithm based on the theory. This algorithm approximates the shortest basis of the first homology group. Finally, we present some results that were computed using our implementation of the algorithm in the Julia programming language. We test the algorithm on a few synthetic data set and one, larger, more realistic data set.

• Keywords: Computational toplogy, topological data analysis, algorithms, homology, persistent homology.