Polynomial-sized topological approximations using the permutahedron

DOI10.4230/LIPICS.SOCG.2016.31MaRDI QIDQ3132865zbMATH OpenOpenAlexFDO

Authors Aruni Choudhary, Michael Kerber, Sharath Raghvendra

Publication date 30 January 2018

Full work available at URL https://arxiv.org/abs/1601.02732

zbMATH Keywords

persistent homologytopological data analysisapproximation algorithmspermutahedronsimplicial approximation

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

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(dlogk)}$ simplices of dimension $k$ or lower. In conjunction with dimension reduction techniques, our approach yields a $O(mathrmpolylog(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 v{C}ech filtration has to contain $n^{Omega(loglogn)}$ features, provided that $epsilon<frac1lo{g}^{1+c}n$ for $cin(0,1)$.

Recommendations

• Polynomial-sized topological approximations using the permutahedron
• Improved approximate Rips filtrations with shifted integer lattices
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Topological inference via meshing

Cited in

(8)

• Strong Collapse for Persistence
• Barcodes of towers and a streaming algorithm for persistent homology
• Polyhedral perturbations that preserve topological form
• Polynomial-sized topological approximations using the permutahedron
• Computing persistent homology of flag complexes via strong collapses
• Improved topological approximations by digitization
• Improved approximate Rips filtrations with shifted integer lattices
• Tracing Isomanifolds in \(\mathbb{R}\) ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations

This page was built for publication: Polynomial-sized topological approximations using the permutahedron

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132865)