Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics
Preprint
Abstract
The Vietoris-Rips filtration, the standard filtration on metric data in topological data analysis, is notoriously sensitive to outliers. Sheehy's subdivision-Rips bifiltration $\mathcal{SR}(-)$ is a density-sensitive refinement that is robust to outliers in a strong sense, but whose 0-skeleton has exponential size. For $X$ a finite metric space of constant doubling dimension and fixed $ε>0$, we construct a $(1+ε)$-homotopy interleaving approximation of $\mathcal{SR}(X)$ whose $k$-skeleton has size $O(|X|^{k+2})$. For $k\geq 1$ constant, the $k$-skeleton can be computed in time $O(|X|^{k+3})$.
Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- On the Stability of Interval Decomposable Persistence ModulesDiscrete & Computational Geometry, 2021
- Barcodes of Towers and a Streaming Algorithm for Persistent HomologyDiscrete & Computational Geometry, 2018
- The Rank Invariant Stability via Interleavings2018
- Polynomial-Sized Topological Approximations Using the PermutahedronDiscrete & Computational Geometry, 2017
- Approximating persistent homology in Euclidean space through collapsesApplicable Algebra in Engineering, Communication and Computing, 2015
- Robust Statistics, Hypothesis Testing, and Confidence Intervals for Persistent Homology on Metric Measure SpacesFoundations of Computational Mathematics, 2014
- Linear-Size Approximations to the Vietoris–Rips FiltrationDiscrete & Computational Geometry, 2013
- The Theory of Multidimensional PersistenceDiscrete & Computational Geometry, 2009
- Small Hop-diameter Sparse Spanners for Doubling MetricsDiscrete & Computational Geometry, 2008
- Lectures on Analysis on Metric Spaces2001