License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.31
URN: urn:nbn:de:0030-drops-59236
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5923/
Go to the corresponding LIPIcs Volume Portal

Choudhary, Aruni ; Kerber, Michael ; Raghvendra, Sharath

Polynomial-Sized Topological Approximations Using the Permutahedron

pdf-format:
LIPIcs-SoCG-2016-31.pdf (0.5 MB)

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 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(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 Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n) for c in (0,1).

BibTeX - Entry

@InProceedings{choudhary_et_al:LIPIcs:2016:5923,
  author =	{Aruni Choudhary and Michael Kerber and Sharath Raghvendra},
  title =	{{Polynomial-Sized Topological Approximations Using the Permutahedron}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5923},
  URN =		{urn:nbn:de:0030-drops-59236},
  doi =		{10.4230/LIPIcs.SoCG.2016.31},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Simplicial Approximation, Permutahedron, Approximation Algorithms}
}

Keywords: Persistent Homology, Topological Data Analysis, Simplicial Approximation, Permutahedron, Approximation Algorithms
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI