SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch-collapse
From MaRDI portal
Publication:4606305
DOI10.4230/LIPICS.ESA.2016.35zbMATH Open1397.68221arXiv1609.07517MaRDI QIDQ4606305FDOQ4606305
Authors: Dayu Shi, Yusu Wang, Tamal K. Dey 
Publication date: 2 March 2018
Abstract: In topological data analysis, a point cloud data P extracted from a metric space is often analyzed by computing the persistence diagram or barcodes of a sequence of Rips complexes built on indexed by a scale parameter. Unfortunately, even for input of moderate size, the size of the Rips complex may become prohibitively large as the scale parameter increases. Starting with the Sparse Rips filtration introduced by Sheehy, some existing methods aim to reduce the size of the complex so as to improve the time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high dimensional data. In this paper, we investigate the advantages and limitations of existing approaches. Based on insights gained from the experiments, we propose an efficient new algorithm, called SimBa, for approximating the persistent homology of Rips filtrations with quality guarantees. Our new algorithm leverages a batch collapse strategy as well as a new sparse Rips-like filtration. We experiment on a variety of low and high dimensional data sets. We show that our strategy presents a significant size reduction, and our algorithm for approximating Rips filtration persistence is order of magnitude faster than existing methods in practice.
Full work available at URL: https://arxiv.org/abs/1609.07517
Recommendations
- SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch collapse
- Linear-size approximations to the Vietoris-Rips filtration
- Linear-size approximations to the Vietoris-Rips filtration
- Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
- Topological inference via meshing
Other homology theories in algebraic topology (55N35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cited In (13)
- Divisive cover
- Sparse Dowker nerves
- Barcodes of towers and a streaming algorithm for persistent homology
- Linear-size approximations to the Vietoris-Rips filtration
- Quantitative simplification of filtered simplicial complexes
- Alpha magnitude
- Strong Collapse for Persistence
- Protein Classification with Improved Topological Data Analysis.
- Strong collapse and persistent homology
- Generalized persistence algorithm for decomposing multiparameter persistence modules
- Computing Persistent Homology of Flag Complexes via Strong Collapses
- Filtration simplification for persistent homology via edge contraction
- Compression for \(2\)-parameter persistent homology
Uses Software
This page was built for publication: SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch-collapse
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606305)
