Collapses and persistent homology - Archive ouverte HAL Access content directly
Theses Year : 2020

Collapses and persistent homology

Effondrements et homologie persistante

(1)
1

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 complexes of 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 \textit{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 othertypes 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 all its simplices, which saves a lot ofspace 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 the 1-skeleton of the complex and the resulting complex is also a flag complex. We show that if we restrict 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 coreflag 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 extremelyefficient. 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 the 1-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 F^c with the same persistence. Here again, we only use the 1-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 particular the method using edge collapse performs the best among all known methods including the strong collapse approach. Finally, we can compromizebetween precision and time by choosing the number of simplicial complexes of the sequence we strong collapse.
Dans cette thèse, nous introduisons deux nouvelles approches pour calculer l'homologie persistante(HP) d'une séquence de complexes simpliciaux. L'idée de base est de simplifier les complexes de la séquence d'entrée en utilisant des types spéciaux de collapses (effondrement), les collapses forts et les collapses d'arêtes, et de calculer l'HP d'une séquence réduite de plus petite taille qui a la même HP que la séquence initiale. Notre première approche utilise les collapses forts introduits par J. Barmak et E. Miniam [DCG (2012)]. Un collapse fort supprime les sommets dits dominés d'un complexe simplicial. Notre approche utilisant les collapses forts a plusieurs caractéristiques qui la distinguent des travaux antérieurs. La méthode n'est pas limitée aux filtrations (c'est-à-dire aux séquences de sous-complexes simpliciaux imbriqués) mais fonctionne pour d'autres types de séquences comme les tours et les zigzags. Par ailleurs, pour implémenter les collapses forts, il suffit de représenter les simplexes maximaux du complexe, et pas l'ensemble de tous ses simplexes, ce qui économise beaucoup d'espace et de temps. De plus, les complexes de la séquence peuvent être collapsés indépendamment et en parallèle.Dans le cas des complexes en drapeaux (flag complexes), les collapses forts peuvent être réalisés sur le 1-squelette du complexe et le complexe résultat est également un complexe en drapeau. Nous montrons que si l'on restreint la classe des complexes simpliciaux aux complexes en drapeaux, on peut améliorer la complexité en temps et en espace de facon décisive par rapport aux travaux antérieurs. Lorsque les collapses forts sont appliqués aux complexes d'une tour de complexes en drapeau, nous obtenons une séquence réduite qui est aussi une tour de complexes en drapeau que nous appelons le coeur de la tour. Nous convertissons ensuite le coeur de la tour en une filtration équivalente pour calculer son HP. Là encore, nous n'utilisons que les 1-squelettes des complexes. La méthode résultante est simple et extrêmement efficace.Nous étendons la notion de sommet dominé au cas de simplexes de dimension quelconque. Le concept d'arête dominée apparait très puissant et nous l'étudions dans le cas des complexes en drapeaux de faconplus détaillée. Nous montrons que les collapses d'arêtes (suppression des arêtes dominées) dans un complexe en drapeaux peut être effectué, comme précédemment, en utilisant uniquement le 1-squelette du complexe. En outre, le complexe résiduel est également un complexe de drapeaux. Ensuite, nous montrons que, comme dans le cas des collapses forts, on peut utiliser les collapses d'arêtes pour réduire une filtration de complexes en drapeaux en une filtration de complexes en drapeaux plus petite qui a la même HP. Là encore, nous utilisons uniquement le 1-squelettes des complexes.Comme l'ont démontré de nombreuses expériences sur des données publiques, les approches développées sont extrêmement rapides et efficaces en mémoire. En particulier, la méthode utilisant les collapses d'arêtes offre de meilleures performances que toutes les méthodes connues, y compris l'approche par collapses forts. Enfin, nous pouvons faire des compromis entre précision et temps de calcul en choisissant le nombre de complexes simpliciaux de la séquence à collapser.
Fichier principal
Vignette du fichier
2020COAZ4033.pdf (1.96 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)

Dates and versions

tel-02962587 , version 1 (09-10-2020)
tel-02962587 , version 2 (08-02-2021)

Identifiers

  • HAL Id : tel-02962587 , version 2

Cite

Siddharth Pritam. Collapses and persistent homology. Computational Geometry [cs.CG]. Université Côte d'Azur, 2020. English. ⟨NNT : 2020COAZ4033⟩. ⟨tel-02962587v2⟩
274 View
276 Download

Share

Gmail Facebook Twitter LinkedIn More