# Gaussian Sketching yields a J-L Lemma in RKHS

arXiv: https://arxiv.org/abs/1908.05818 · HTML: https://mlsanity.com/paper/1908.05818/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2019.

## Built on by (most cited first, 6 of 6)

- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [An Efficient One-Class SVM for Anomaly Detection in the Internet of Things](https://mlsanity.com/paper/2104.11146/) (2021)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [Robust and Provable Guarantees for Sparse Random Embeddings](https://mlsanity.com/paper/2202.10815/) (2022)

## Abstract (arXiv)

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 ZboldsymbolK 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 langle f, g rangleSigma doteq langle f, Sigma3 g ranglemathcal H, where Sigma 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 Xii=1N of size N, we can build the Gram matrix boldsymbol K on a much smaller subsample of size nll N, so that the sketch Zboldsymbol K is very cheap to obtain and subsequently apply as a projection operator on the original data Xii=1N. We verify these insights empirically on synthetic data, and on real-world clustering applications.