Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels
Arya, Shreya ; Boissonnat, Jean-Daniel ; Dutta, Kunal
HAL, hal-01950051 / Harvested from HAL
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.
Publié le : 2018-12-10
Classification:  Distance to measure,  Gaussian Kernel,  Persistent Homology,  Dimension Reduction,  Johnson-Lindenstrauss,  [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG],  [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],  [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT],  [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT]
@article{hal-01950051,
     author = {Arya, Shreya and Boissonnat, Jean-Daniel and Dutta, Kunal},
     title = {Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels},
     journal = {HAL},
     volume = {2018},
     number = {0},
     year = {2018},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01950051}
}
Arya, Shreya; Boissonnat, Jean-Daniel; Dutta, Kunal. Persistent Homology with Dimensionality Reduction: k-Distance vs Gaussian Kernels. HAL, Tome 2018 (2018) no. 0, . http://gdmltest.u-ga.fr/item/hal-01950051/