HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Dimensionality reduction for k-distance applied to persistent homology

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. Comp. 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 Geometry, 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.
Complete list of metadata

Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Wednesday, November 3, 2021 - 1:46:14 PM
Last modification on : Friday, March 25, 2022 - 12:17:36 PM


Publisher files allowed on an open archive



Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta, Martin Lotz. Dimensionality reduction for k-distance applied to persistent homology. Journal of Applied and Computational Topology, Springer, 2021, 5, pp.671-691. ⟨10.1007/s41468-021-00079-x⟩. ⟨hal-03412594⟩



Record views


Files downloads