Zigzag Persistence via Reflections and Transpositions

Clément Maria 1 Steve Oudot 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We introduce a new algorithm for computing zigzag persis-tence, designed in the same spirit as the standard persistence algorithm. Our algorithm reduces a single matrix, maintains an explicit set of chains encoding the persistent homology of the current zigzag, and updates it under simplex insertions and removals. The total worst-case running time matches the usual cubic bound. A noticeable difference with the standard persistence al-gorithm is that we do not insert or remove new simplices "at the end" of the zigzag, but rather "in the middle". To do so, we use arrow reflections and transpositions, in the same spirit as reflection functors in quiver theory. Our analysis introduces new kinds of reflections in quiver representation theory: the "injective and surjective diamonds". It also in-troduces the "transposition diamond" which models arrow transpositions. For each type of diamond we are able to predict the changes in the interval decomposition and as-sociated compatible bases. Arrow transpositions have been studied previously in the context of standard persistent ho-mology, and we extend the study to the context of zigzag persistence. For both types of transformations, we provide simple procedures to update the interval decomposition and associated compatible homology basis.
Type de document :
Communication dans un congrès
ACM-SIAM Symposium on Discrete Algorithms, Jan 2015, San Diego, United States. 2015, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 〈http://www.siam.org/meetings/da15/〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01091949
Contributeur : Steve Oudot <>
Soumis le : lundi 8 décembre 2014 - 07:05:14
Dernière modification le : samedi 18 février 2017 - 01:14:40
Document(s) archivé(s) le : lundi 9 mars 2015 - 10:25:42

Fichier

soda_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01091949, version 1

Collections

Citation

Clément Maria, Steve Oudot. Zigzag Persistence via Reflections and Transpositions. ACM-SIAM Symposium on Discrete Algorithms, Jan 2015, San Diego, United States. 2015, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 〈http://www.siam.org/meetings/da15/〉. 〈hal-01091949〉

Partager

Métriques

Consultations de
la notice

324

Téléchargements du document

105