Computing topological persistence for simplicial maps (extended abstract)

DOI10.1145/2582112.2582165zbMATH Open1395.68299arXiv1208.5018OpenAlexW1970454523MaRDI QIDQ4635559FDOQ4635559

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)

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.

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

Recommendations

• An output-sensitive algorithm for persistent homology
• Computing persistent homology
• Computing persistent homology
• An output-sensitive algorithm for persistent homology
• The compressed annotation matrix: an efficient data structure for computing persistent cohomology

zbMATH Keywords

topological data analysiscohomologyhomologytopological persistencesimplicial maps

Mathematics Subject Classification ID

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

Cited In (36)

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

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)