Skip to Main content Skip to Navigation
Theses

Collapses and Persistent Homology

Siddharth Pritam 1
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this thesis, we introduce two new approaches to compute the Persistent Homology (PH) of a sequence of simplicial complexes. The basic idea is to simplify the complexesof the input sequence by using special types of collapses (strong and edge collapse) and to compute the PH of an induced sequence of smaller size that has the same PH as the initial one. Our first approach uses strong collapse which is introduced by J. Barmak and E. Miniam [DCG (2012)]. Strong collapse comprises of removal of special vertices called dominated vertices from a simplicial complex. Our approach with strong collapse has several salient features that distinguishes it from previous work. It is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. To strong collapse a simplicial complex, we only need to store the maximal simplices of the complex, not the full set of allits simplices, which saves a lot of space and time. Moreover, the complexes in the sequence can be strong collapsed independently and in parallel. In the case of flag complexes strong collapse can be performed over the1-skeletonof the complex and the resulting complex is also a flag complex. We show that if were strict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient. We extend the notions of dominated vertex to a simplex of any dimension. Domination of edges appear to be very powerful and we study it in the case of flag complexes in more detail. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the1-skeleton of the complex as well. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration F to a smaller flag filtration $Fc$ with the same persistence. Here again, we only use the1-skeletons of the complexes. As a result and as demonstrated by numerous experiments on publicly available data sets, our approaches are extremely fast and memory efficient in practice. In particularthe method using edge collapse performs the best among all known methods including the strong collapse approach. Finally, we can compromize between precision and time by choosing the number of simplicial complexes of the sequence we strong collapse.
Document type :
Theses
Complete list of metadatas

Cited literature [51 references]  Display  Hide  Download

https://hal.inria.fr/tel-02962587
Contributor : Siddharth Pritam <>
Submitted on : Friday, October 9, 2020 - 1:00:57 PM
Last modification on : Saturday, October 10, 2020 - 3:35:52 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02962587, version 1

Collections

Citation

Siddharth Pritam. Collapses and Persistent Homology. Computer Science [cs]. UCA; Inria, 2020. English. ⟨tel-02962587⟩

Share

Metrics

Record views

62

Files downloads

47