2026-07-23T04:53:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12168 2024-03-06T10:49:36Z ddc:004 open_access

Dimensionality Reduction for k-Distance Applied to Persistent Homology Arya, Shreya Boissonnat, Jean-Daniel Dutta, Kunal Lotz, Martin Dimensionality reduction Johnson-Lindenstrauss lemma Topological Data Analysis Persistent Homology k-distance distance to measure Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Čech filtration of P for the k-distance, and investigate the effectiveness of dimensionality reduction for this problem, answering an open question of Sheehy [Proc. SoCG, 2014]. We show that any linear transformation that preserves pairwise distances up to a (1±ε) multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of (1-ε)^{-1}. Our results also show that the Vietoris-Rips and Delaunay filtrations for the k-distance, as well as the Čech filtration for the approximate k-distance of Buchet et al. are preserved up to a (1±ε) factor. We also prove extensions of our main theorem, for point sets (i) lying in a region of bounded Gaussian width or (ii) on a low-dimensional manifold, obtaining the target dimension bounds of Lotz [Proc. Roy. Soc. , 2019] and Clarkson [Proc. SoCG, 2008 ] respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shreya Arya and Jean-Daniel Boissonnat and Kunal Dutta and Martin Lotz 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.10 urn:nbn:de:0030-drops-121682 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.10 eng https://creativecommons.org/licenses/by/3.0/legalcode