Improved topological approximations by digitization

DOI10.1137/1.9781611975482.166MaRDI QIDQ5236356zbMATH OpenOpenAlexFDO

Authors Aruni Choudhary, Michael Kerber, Sharath Raghvendra

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational aspects of digital topology (68U03)

Abstract: v{C}ech complexes are useful simplicial complexes for computing and analyzing topological features of data that lies in Euclidean space. Unfortunately, computing these complexes becomes prohibitively expensive for large-sized data sets even for medium-to-low dimensional data. We present an approximation scheme for $(1+epsilon)$-approximating the topological information of the v{C}ech complexes for $n$ points in $mathbb{R}^d$, for $epsilonin(0,1]$. Our approximation has a total size of $nleft(frac1epsilonight{)}^{O(d)}$ for constant dimension $d$, improving all the currently available $(1+epsilon)$-approximation schemes of simplicial filtrations in Euclidean space. Perhaps counter-intuitively, we arrive at our result by adding additional $nleft(frac1epsilonight{)}^{O(d)}$ sample points to the input. We achieve a bound that is independent of the spread of the point set by pre-identifying the scales at which the v{C}ech complexes changes and sampling accordingly.

Recommendations

• Approximate Čech Complex in Low and High Dimensions
• Approximating persistent homology in Euclidean space through collapses
• Topological inference via meshing
• Polynomial-sized topological approximations using the permutahedron
• Polynomial-sized topological approximations using the permutahedron

Cited in

(10)

• Topological grammars for data approximation
• Compression for \(2\)-parameter persistent homology
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Sparse Dowker nerves
• Approximating persistent homology in Euclidean space through collapses
• Improved Scale-Invariant Moments for Deformation Digits
• Topological inference via meshing
• Universality of the homotopy interleaving distance
• Sparse higher order Čech filtrations
• A sparse Delaunay filtration

This page was built for publication: Improved topological approximations by digitization

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