Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

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.
Fichier principal
Vignette du fichier
arya-boissonnat-dutta.pdf (494.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01950051 , version 1 (10-12-2018)

Identifiants

  • HAL Id : hal-01950051 , version 1

Citer

Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta. Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels. 2018. ⟨hal-01950051v1⟩
289 Consultations
364 Téléchargements

Partager

Gmail Facebook X LinkedIn More