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 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 SR (X) whose k-skeleton has size O (|X|^k+2). For k 1 constant, the k-skeleton can be computed in time O (|X|^k+3).