Polynomial-Sized Topological Approximations Using The Permutahedron
| Autor: | Michael Kerber, Sharath Raghvendra, Aruni Choudhary |
|---|---|
| Přispěvatelé: | Computer Science |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences 050101 languages & linguistics 68W01 68W25 55U99 Lattice (group) Topological data analysis Discrete geometry 02 engineering and technology Algebraic topology Topology Upper and lower bounds Theoretical Computer Science Combinatorics 0202 electrical engineering electronic engineering information engineering Filtration (mathematics) FOS: Mathematics Discrete Mathematics and Combinatorics Algebraic Topology (math.AT) 0501 psychology and cognitive sciences 55U10 Mathematics - Algebraic Topology Persistent homology Simplicial approximation Mathematics 060201 languages & linguistics Polynomial (hyperelastic model) Permutohedron 000 Computer science knowledge general works 05 social sciences 06 humanities and the arts Approximation algorithms 68W25 Metric space Computational Theory and Mathematics 0602 languages and literature Computer Science Permutahedron Computer Science - Computational Geometry 020201 artificial intelligence & image processing Geometry and Topology 11H06 |
| Zdroj: | Discrete & Computational Geometry 32nd International Symposium on Computational Geometry Leibniz International Proceedings in Informatics |
| Popis: | 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 $n2^{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 \v{C}ech filtration has to contain $n^{\Omega(\log\log n)}$ features, provided that $\epsilon Comment: 24 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|