Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Polynomial-Sized Topological Approximations Using The Permutahedron

Choudhary, A., Kerber, M., & Raghvendra, S. (2016). Polynomial-Sized Topological Approximations Using The Permutahedron. Retrieved from http://arxiv.org/abs/1601.02732.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1601.02732.pdf (Preprint), 609KB
Name:
arXiv:1601.02732.pdf
Beschreibung:
File downloaded from arXiv at 2016-07-13 14:58
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Choudhary, Aruni1, Autor           
Kerber, Michael1, Autor           
Raghvendra, Sharath2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Geometry, cs.CG,Mathematics, Algebraic Topology, math.AT,
 Zusammenfassung: 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 <\frac{1}{\log^{1+c} n}$ for $c\in(0,1)$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2016-01-122016-04-012016
 Publikationsstatus: Online veröffentlicht
 Seiten: 24 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1601.02732
URI: http://arxiv.org/abs/1601.02732
BibTex Citekey: ChoudharyarXiv2016
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: