Polynomial-Sized Topological Approximations Using The Permutahedron

Abstract

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 with at most $n{2}^{O(d\log k)}$ simplices of dimension $k$ or lower. 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 approximate filtration: we construct a point set for which every $(1+\epsilon )$-approximation of the Čech filtration has to contain $n^{\Omega (\log \log n)}$ features, provided that $\epsilon <\frac{1}{{\log }^{1+c}n}$ for $c\in (0,1)$.

arXiv comment24 pages, 1 figure