Computing topological persistence for simplicial maps (extended abstract)

DOI10.1145/2582112.2582165MaRDI QIDQ4635559zbMATH OpenOpenAlexFDO

Authors Fengtao Fan, Yusu Wang, Tamal K. Dey

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

cohomologyhomologysimplicial mapstopological data analysistopological persistence

Mathematics Subject Classification ID

Other homology theories in algebraic topology (55N35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Algorithms for persistent homology and zigzag persistent homology are well-studied for persistence modules where homomorphisms are induced by inclusion maps. In this paper, we propose a practical algorithm for computing persistence under $mathbb{Z}_2$ coefficients for a sequence of general simplicial maps and show how these maps arise naturally in some applications of topological data analysis. First, we observe that it is not hard to simulate simplicial maps by inclusion maps but not necessarily in a monotone direction. This, combined with the known algorithms for zigzag persistence, provides an algorithm for computing the persistence induced by simplicial maps. Our main result is that the above simple minded approach can be improved for a sequence of simplicial maps given in a monotone direction. A simplicial map can be decomposed into a set of elementary inclusions and vertex collapses--two atomic operations that can be supported efficiently with the notion of simplex annotations for computing persistent homology. A consistent annotation through these atomic operations implies the maintenance of a consistent cohomology basis, hence a homology basis by duality. While the idea of maintaining a cohomology basis through an inclusion is not new, maintaining them through a vertex collapse is new, which constitutes an important atomic operation for simulating simplicial maps. Annotations support the vertex collapse in addition to the usual inclusion quite naturally. Finally, we exhibit an application of this new tool in which we approximate the persistence diagram of a filtration of Rips complexes where vertex collapses are used to tame the blow-up in size.

Recommendations

• An output-sensitive algorithm for persistent homology
• Computing persistent homology
• Computing persistent homology
• An output-sensitive algorithm for persistent homology

Cited in

(36)

• Cliques and cavities in the human connectome
• Polynomial-sized topological approximations using the permutahedron
• An output-sensitive algorithm for persistent homology
• HERMES: persistent spectral graph software
• Magnitude meets persistence: homology theories for filtered simplicial sets
• Local computation of homology variations over a construction process
• Computing multiparameter persistent homology through a discrete Morse-based approach
• Evolutionary homology on coupled dynamical systems with applications to protein flexibility analysis
• Quantitative simplification of filtered simplicial complexes
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• The persistent homology of a sampled map: from a viewpoint of quiver representations
• A functorial Dowker theorem and persistent homology of asymmetric networks
• A comparison framework for interleaved persistence modules
• Approximating persistent homology in Euclidean space through collapses
• Barcodes of towers and a streaming algorithm for persistent homology
• A topological approach for protein classification
• Efficient and robust persistent homology for measures
• Homological shape analysis through discrete Morse theory
• SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch collapse
• Strong Collapse for Persistence
• The Persistent Homology of Cyclic Graphs
• Persistence of Conley-Morse graphs in combinatorial dynamical systems
• Computing persistent homology of flag complexes via strong collapses
• Protein classification with improved topological data analysis
• Improved approximate Rips filtrations with shifted integer lattices
• Persistent homology of Morse decompositions in combinatorial dynamics
• Strong collapse and persistent homology
• Universality of the homotopy interleaving distance
• Computing hypergraph homology
• A generalization of the persistent Laplacian to simplicial maps
• Adaptive approximation of persistent homology
• Persistent homology classifies parameter dependence of patterns in Turing systems
• Sparse higher order Čech filtrations
• Tracking the persistence of harmonic chains: barcode and stability
• Zigzag zoology: Rips zigzags for homology inference
• The persistent homology of a self-map

This page was built for publication: Computing topological persistence for simplicial maps (extended abstract)

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