Polynomial-sized topological approximations using the permutahedron

DOI10.4230/LIPICS.SOCG.2016.31zbMATH Open1387.68251arXiv1601.02732OpenAlexW2962690439MaRDI QIDQ3132865FDOQ3132865

Aruni Choudhary, Sharath Raghvendra, Michael Kerber

Publication date: 30 January 2018

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)$.

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

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
• Linear-size approximations to the Vietoris-Rips filtration

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)

Cited In (7)

• Barcodes of towers and a streaming algorithm for persistent homology
• Polynomial-sized topological approximations using the permutahedron
• Strong Collapse for Persistence
• Polyhedral perturbations that preserve topological form
• Improved Approximate Rips Filtrations with Shifted Integer Lattices
• Tracing Isomanifolds in \(\mathbb{R}\) ^d in Time Polynomial in d using Coxeter–Freudenthal–Kuhn Triangulations
• Computing Persistent Homology of Flag Complexes via Strong Collapses

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)