Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910582278455296 |
|---|---|
| author | Lesnick, Michael McCabe, Kenneth |
| author_facet | Lesnick, Michael McCabe, Kenneth |
| contents | 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})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16716 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics Lesnick, Michael McCabe, Kenneth Algebraic Topology Computational Geometry 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})$. |
| title | Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics |
| topic | Algebraic Topology Computational Geometry |
| url | https://arxiv.org/abs/2408.16716 |