Zigzag Zoology: Rips Zigzags for Homology Inference - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2012

Zigzag Zoology: Rips Zigzags for Homology Inference

(1) , (1)
1
Steve Oudot
  • Function : Author
  • PersonId : 845393
Donald Sheehy
  • Function : Author
  • PersonId : 932989

Abstract

For points sampled near a compact set X, the persistence barcode of the Rips filtration built from the sample contains information about the homology of X as long as X satisfies some geometric assumptions. The Rips filtration is prohibitively large, however zigzag persistence can be used to keep the size linear. We present several species of Rips-like zigzags and compare them with respect to the signal-to-noise ratio, a measure of how well the underlying homology is represented in the persistence barcode relative to the noise in the barcode at the relevant scales. Some of these Rips-like zigzags have been available as part of the Dionysus library for several years while others are new. Interestingly, we show that some species of Rips zigzags will exhibit less noise than the (non-zigzag) Rips filtration itself. Thus, the Rips zigzag can offer improvements in both size complexity and signal-to-noise ratio. Along the way, we develop new techniques for manipulating and comparing persistence barcodes from zigzag modules. We give methods for reversing arrows and removing spaces from a zigzag. We also discuss factoring zigzags and a kind of interleaving of two zigzags that allows their barcodes to be compared. These techniques were developed to provide our theoretical analysis of the signal-to-noise ratio of Rips-like zigzags, but they are of independent interest as they apply to zigzag modules generally.
Pour des points échantillonnés près d'un compact X, le code-barre de la filtration de Rips construite sur les points contient de l'information à propos de l'homologie de X sous certaines hypothèses géométriques. Toutefois, le coût de construction de la filtration de Rips est prohibitif, mais la persistence des zigzags peut permettre de le rendre linéaire en le nombre de points de données. Nous présentons plusieurs types de zigzags basés sur des complexes de Rips, et nous les comparons à l'aune de leur rapport signal sur bruit. Certains de ces zigzags sont disponibles dans la bibliothèque Dionysus depuis plusieurs années, tandis que d'autres sont nouveaux. Il est intéressant d'observer que certains ont des codes-barres avec significativement moins de bruit que celui de la filtration de Rips standard. Ainsi, les zigzags à base de complexes de Rips permettent-ils non seulement de réduire la complexité mais également d'améliorer le résultat de l'approche. Dans notre analyse nous développons de nouveaux outils pour manipuler les zigzags et comparer leurs codes-barres. En particulier, nous fournissons des méthodes pour inverser des flèches ou enlever des espaces dans un zigzag, tout en contrôlant l'impact sur son code-barre. Nous parlons également de factorisation et d'entrelacement de zigzags. Ces outils sont la clef de voûte de notre analyse, et ils présentent un intérêt indépendant puisqu'ils s'appliquent aux zigzags en général, et non pas seulement à ceux étudiés ici.
Fichier principal
Vignette du fichier
RR-8141.pdf (929.48 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00755280 , version 1 (23-11-2012)

Identifiers

  • HAL Id : hal-00755280 , version 1

Cite

Steve Oudot, Donald Sheehy. Zigzag Zoology: Rips Zigzags for Homology Inference. [Research Report] RR-8141, INRIA. 2012, pp.48. ⟨hal-00755280⟩
377 View
318 Download

Share

Gmail Facebook Twitter LinkedIn More