2019/08/16 by Samory Kpotufe, Bharath K. Sriperumbudur, Kpotufe, Samory +1 · 1 citation
Computer Science · Engineering · #Face and Expression Recognition #Blind Source Separation Techniques #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1908.05818
The main contribution of the paper is to show that Gaussian sketching of a kernel-Gram matrix \boldsymbol K yields an operator whose counterpart in an RKHS \mathcal H, is a random projection operator---in the spirit of Johnson-Lindenstrauss (J-L) lemma. To be precise, given a random matrix Z with i.i.d. Gaussian entries, we show that a sketch Z\boldsymbolK corresponds to a particular random operator in (infinite-dimensional) Hilbert space \mathcal H that maps functions f ∈ \mathcal H to a low-dimensional space \mathbb Rd, while preserving a weighted RKHS inner-product of the form ⟨ f, g ⟩Σ \doteq ⟨ f, Σ3 g ⟩\mathcal H, where Σ is the covariance operator induced by the data distribution. In particular, under similar assumptions as in kernel PCA (KPCA), or kernel k-means (K-k-means), well-separated subsets of feature-space \K(⋅, x): x ∈ \cal X\ remain well-separated after such operation, which suggests similar benefits as in KPCA and/or K-k-means, albeit at the much cheaper cost of a random projection. In particular, our convergence rates suggest that, given a large dataset \Xi\i=1N of size N, we can build the Gram matrix \boldsymbol K on a much smaller subsample of size n≪ N, so that the sketch Z\boldsymbol K is very cheap to obtain and subsequently apply as a projection operator on the original data \Xi\i=1N. We verify these insights empirically on synthetic data, and on real-world clustering applications.