Improved Topological Approximations by Digitization

Abstract

Čech complexes are useful simplicial complexes for computing and analyzing topological features of data that lies in Euclidean space. Unfortunately, computing these complexes becomes prohibitively expensive for large-sized data sets even for medium-to-low dimensional data. We present an approximation scheme for $(1+ε)$-approximating the topological information of the Čech complexes for $n$ points in $\mathbb{R}^d$, for $ε\in(0,1]$. Our approximation has a total size of $n\left(\frac{1}ε\right)^{O(d)}$ for constant dimension $d$, improving all the currently available $(1+ε)$-approximation schemes of simplicial filtrations in Euclidean space. Perhaps counter-intuitively, we arrive at our result by adding additional $n\left(\frac{1}ε\right)^{O(d)}$ sample points to the input. We achieve a bound that is independent of the spread of the point set by pre-identifying the scales at which the Čech complexes changes and sampling accordingly.

To appear at SODA 2019