Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels
Résumé
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 − ε)$ factor with target dimension $O(k log n/ε 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/ε 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 − ε)$ factor.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...