The Library
Dimensionality reduction for k-distance applied to persistent homology
Tools
Arya, Shreya, Boissonat, Jean-Daniel, Dutta, Kunal and Lotz, Martin (2021) Dimensionality reduction for k-distance applied to persistent homology. Journal of Applied and Computational Topology, 5 . pp. 671-691. doi:10.1007/s41468-021-00079-x ISSN 2367-1726.
|
PDF
WRAP-Dimensionality-reduction-k-distance-applied-persistent-homology-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (447Kb) | Preview |
|
PDF
WRAP-Dimensionality-reduction-k-distance-applied-persistent-homology-2021.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (542Kb) |
Official URL: https://doi.org/10.1007/s41468-021-00079-x
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 (The persistent homology of distance functions under random projection. In Cheng, Devillers (eds), 30th Annual Symposium on Computational Geometry, SOCG’14, Kyoto, Japan, June 08–11, p 328, ACM, 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. [J Comput Geom, 58:70–96, 2016] 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 submanifold, obtaining embeddings having the dimension bounds of Lotz (Proc R Soc A Math Phys Eng Sci, 475(2230):20190081, 2019) and Clarkson (Tighter bounds for random projections of manifolds. In Teillaud (ed) Proceedings of the 24th ACM Symposium on Computational Geom- etry, College Park, MD, USA, June 9–11, pp 39–48, ACM, 2008) respectively. Our results also work in the terminal dimensionality reduction setting, where the distance of any point in the original ambient space, to any point in P, needs to be approximately preserved.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Geometry -- Data processing, Homology theory, Topology | |||||||||||||||
Journal or Publication Title: | Journal of Applied and Computational Topology | |||||||||||||||
Publisher: | Springer | |||||||||||||||
ISSN: | 2367-1726 | |||||||||||||||
Official Date: | 2 November 2021 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 5 | |||||||||||||||
Page Range: | pp. 671-691 | |||||||||||||||
DOI: | 10.1007/s41468-021-00079-x | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 19 October 2021 | |||||||||||||||
Date of first compliant Open Access: | 4 November 2021 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Related URLs: | ||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year