The Library
Dimensionality reduction for k-distance applied to persistent homology
Tools
Tools
Tools
Arya, Shreya, Boissonnat, Jean-Daniel, Dutta, Kunal and Lotz, Martin (2020) Dimensionality reduction for k-distance applied to persistent homology. In: 6th International Symposium on Computational Geometry (SoCG 2020), Zürich, Switzerland, 23-26 June 2020. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 164 10:1-10:15. ISBN 9783959771436. doi:10.4230/LIPIcs.SoCG.2020.10 ISSN 1868-8969.
|
PDF
WRAP-dimensionality-reduction-k-distance-applied-persistent-homology-Lotz-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (483Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2020.10
Abstract
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.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
| Library of Congress Subject Headings (LCSH): | Dimension reduction (Statistics), Topological dynamics , Homology theory, K-theory | |||||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959771436 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 2020 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 164 | |||||||||
| Page Range: | 10:1-10:15 | |||||||||
| DOI: | 10.4230/LIPIcs.SoCG.2020.10 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 3 January 2019 | |||||||||
| Date of first compliant Open Access: | 16 January 2019 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 6th International Symposium on Computational Geometry (SoCG 2020) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Zürich, Switzerland | |||||||||
| Date(s) of Event: | 23-26 June 2020 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
