Dimensionality reduction for k-distance applied to persistent homology - Archive ouverte HAL Access content directly
Journal Articles Journal of Applied and Computational Topology Year : 2021

Dimensionality reduction for k-distance applied to persistent homology

(1) , (2) , (3) , (4)
1
2
3
4
Shreya Arya
  • Function : Author
  • PersonId : 1040289
Jean-Daniel Boissonnat
  • Function : Author
  • PersonId : 830857
Kunal Dutta
  • Function : Author
  • PersonId : 1138598
Martin Lotz
  • Function : Author
  • PersonId : 1115618

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.
Fichier principal
Vignette du fichier
DimReducTDA.pdf (447.54 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

hal-03412594 , version 1 (03-11-2021)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More