SimBa
- 30 January 2019
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
- Vol. 24 (1), 1-16
- https://doi.org/10.1145/3284360
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 P 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 to improve time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high-dimensional data. In this article, 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 datasets. We show that our strategy presents a significant size reduction and that our algorithm for approximating Rips filtration persistence is an order of magnitude faster than existing methods in practice.Keywords
Funding Information
- NSF (CCF-1318595 and CCF-1526513)
This publication has 23 references indexed in Scilit:
- Persistent Cohomology and Circular CoordinatesDiscrete & Computational Geometry, 2011
- Persistent Heat Signature for Pose‐oblivious Matching of Incomplete ModelsComputer Graphics Forum, 2010
- The Theory of Multidimensional PersistenceDiscrete & Computational Geometry, 2009
- Topology and dataBulletin of the American Mathematical Society, 2009
- On the Nonlinear Statistics of Range Image PatchesSIAM Journal on Imaging Sciences, 2009
- Topological analysis of population activity in visual cortexJournal of Vision, 2008
- Stability of Persistence DiagramsDiscrete & Computational Geometry, 2006
- Computing Persistent HomologyDiscrete & Computational Geometry, 2004
- Topological Persistence and SimplificationDiscrete & Computational Geometry, 2002
- A distance for similarity classes of submanifolds of a Euclidean spaceBulletin of the Australian Mathematical Society, 1990