Dimensionality Reduction for k-Distance Applied to Persistent Homology

Given a set P of n points and a constant k, we are interested in computing the persistent homology of the Cech 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 first show using the Johnson-Lindenstrauss lemma, that the persistent homology can be preserved up to a (1 ± e) factor while reducing dimensionality to O(k log n/e2). Our main result shows that the target dimension can be improved to O(logn/e2) under a reasonable and naturally occuring condition. The proof involves a multi-dimensional variant of the Hanson-Wright inequality for subgaussian quadratic forms and works with subgaussian random matrices in the Johnson-Lindenstrauss mapping, which includes the Gaussian matrices of Indyk-Motwani, the sparse random matrices of Achlioptas and the Ailon-Chazelle fast Johnson-Lindenstrauss transform. To provide evidence that our condition encompasses quite general situations, we show that it is satisfied when the points are independently distributed (i) in RD under a subgaussian distribution, or (ii) on a spherical shell in RD with a minimum angular separation, using Gershgorin’s theorem. Our results also show that the JL-mapping preserves up to a (1 ± e) factor, the Rips and Delaunay filtrations for the k-distance, as well as the Cech filtration for the approximate k-distance of Buchet et al.