Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels
Shreya Arya, Jean‐Daniel Boissonnat, Kunal Dutta · 2018
We investigate the effectiveness of dimensionality reduction for computing the persistent homology for both k-distance and kernel distance. For k-distance, we show that the standard 3 Johnson-Lindenstrauss reduction preserves the k-distance, which preserves the persistent homology upto a $1/(1 − e)$ factor with target dimension $O(k log n/e 2$). We also prove a concentration inequality for sums of dependent chi-squared random variables, which, under some conditions, allows the persistent homology to be preserved in $O(log n/e 2)$ dimensions. This answers an open question of Sheehy. For Gaussian kernels, we show that the standard Johnson-Lindenstrauss reduction preserves the persistent homology up to an $4/(1 − e)$ factor.