Polynomial-Sized Topological Approximations Using the Permutahedron
Aruni Choudhary, Michael Kerber, Sharath Raghvendra · Discrete & Computational Geometry · 2017
Classical methods to model topological properties of point clouds, such as the Vietoris–Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in $$\mathbb {R}^d$$ , we obtain a O(d)-approximation whose k-skeleton has size $$n2^{O(d \log k)}$$ per scale and $$n2^{O(d\log d)}$$ in total over all scales. In conjunction with dimension reduction techniques, our approach yields a $$O(\mathrm {polylog} (n))$$ -approximation of size $$n^{O(1)}$$ for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximation: we construct a point set for which every $$(1+\varepsilon )$$ -approximation of the Čech filtration has to contain $$n^{\Omega (\log \log n)}$$ features, provided that $$\varepsilon <\frac{1}{\log ^{1+c} n}$$ for $$c\in (0,1)$$ .