Barcodes of towers and a streaming algorithm for persistent homology

DOI10.4230/LIPICS.SOCG.2017.57zbMATH Open1436.55009arXiv1701.02208MaRDI QIDQ4580135FDOQ4580135

Authors: Michael Kerber, Hannah Schreiber 

Publication date: 13 August 2018

Abstract: A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower.

Full work available at URL: https://arxiv.org/abs/1701.02208

Recommendations

• Barcodes of towers and a streaming algorithm for persistent homology
• Computing persistent homology
• Strong collapse and persistent homology
• Towards minimal barcodes
• Ripser: efficient computation of Vietoris-Rips persistence barcodes

zbMATH Keywords

persistent homologytopological data analysisstreaming algorithmsmatrix reductionsimplicial approximation

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Persistent homology and applications, topological data analysis (55N31)

Cited In (8)

• Barcodes of towers and a streaming algorithm for persistent homology
• Polynomial-sized topological approximations using the permutahedron
• Spatiotemporal barcodes for image sequence analysis
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Strong Collapse for Persistence
• Computing persistent homology of flag complexes via strong collapses
• Persistent extensions and analogous bars: data-induced relations between persistence barcodes
• Improved approximate Rips filtrations with shifted integer lattices

Uses Software

• Gudhi
• PHAT
• SimBa
• Sophia

This page was built for publication: Barcodes of towers and a streaming algorithm for persistent homology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580135)