Choudhary, AruniKerber, MichaelRaghvendra, Sharath2019-08-302019-08-302019-010179-5376http://hdl.handle.net/10919/93322Classical 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 Rd, we obtain a O(d)-approximation whose k-skeleton has size n2O(dlogk) per scale and n2O(dlogd) in total over all scales. In conjunction with dimension reduction techniques, our approach yields a O(polylog(n))-approximation of size nO(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+epsilon)-approximation of the ech filtration has to contain n(loglogn) features, provided that epsilon < 1log1+cn for c(0,1).application/pdfenCreative Commons Attribution 4.0 InternationalPersistent homologyTopological data analysisSimplicial approximationPermutahedronApproximation algorithms55U1011H0668W25Article - Refereedhttps://doi.org/10.1007/s00454-017-9951-26111432-0444