Dimensionality Reduction for Persistent Homology with Gaussian Kernels

Description

Computing persistent homology using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, contrary to the case of computing persistent homology using the Euclidean distance or even the k-distance, it is not known how to compute the persistent homology of high dimensional data using Gaussian kernels. In this paper, we consider a power distance version of the Gaussian kernel distance (GKPD) given by Phillips, Wang and Zheng, and show that the persistent homology of the Čech filtration of P computed using the GKPD is approximately preserved. For datasets in R D , under a relative error bound of ε ∈ (0, 1], we obtain a dimensionality of (i) O(ε −2 log 2 n) for n-point datasets and (ii) O(Dε −2 log(Dr/ε)) for datasets having diameter r (up to a scaling factor). We use two main ingredients. The first one is a new decomposition of the squared radii of Čech simplices using the kernel power distance, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second one is the Random Fourier Features (RFF) map of Rahimi and Recht [NeurIPS 2007], as used by Chen and Phillips [ALT 2017].

Additional details