Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics
<|reference_start|>Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics: 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 $\epsilon>0$, we construct a $(1+\epsilon)$-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})$.<|reference_end|>
@article{lesnick2024sparse,
    title={Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling
  Metrics},
    author={Michael Lesnick and Kenneth McCabe},
    journal={arXiv preprint arXiv:2408.16716},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.16716},
    primaryClass={math.AT cs.CG}
}