Dimensionality reduction for kdistance applied to persistent homology
Authors
Arya, S; Boissonnat, JD; Dutta, K; Lotz, M
Abstract
AbstractGiven 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 kdistance, 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\pm {\varepsilon })$$
(
1
±
ε
)
multiplicative factor, must preserve the persistent homology of the Čech filtration up to a factor of $$(1{\varepsilon })^{1}$$
(
1

ε
)

1
. Our results also show that the VietorisRips and Delaunay filtrations for the kdistance, as well as the Čech filtration for the approximate kdistance of Buchet et al. [J Comput Geom, 58:70–96, 2016] are preserved up to a $$(1\pm {\varepsilon })$$
(
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 lowdimensional 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.