TL;DR
This paper provides a formal theoretical bridge between Gaussian sketching (a popular matrix compression technique) and the Johnson-Lindenstrauss (J-L) Lemma within the context of Reproducing Kernel Hilbert Spaces (RKHS). The authors prove that sketching a kernel Gram matrix is equivalent to applying a random projection operator in the high-dimensional feature space, preserving a specific weighted inner product and enabling much faster versions of Kernel PCA and Kernel k-means.
What Problem Does This Paper Address?
Kernel methods are powerful tools in machine learning because they allow us to operate in high-dimensional (often infinite-dimensional) feature spaces. However, they suffer from a major bottleneck: the Gram matrix $K$ (representing similarities between $N$ data points) is $N \times N$. Operations like Kernel PCA or Kernel k-means typically require $O(N^3)$ or $O(N^2)$ time, which is prohibitive for large datasets.
To speed things up, researchers often use "sketching"—multiplying $K$ by a small random matrix $Z$ to reduce its rank. While this works well in practice, the community lacked a rigorous understanding of what this operation actually does to the underlying functions in the Hilbert space. This paper fills that gap by showing that Gaussian sketching acts as a random projection that preserves the geometry of the data, similar to how the J-L Lemma works for standard Euclidean vectors.
Methods
The authors introduce Kernel-JL (K-JL). Instead of performing expensive eigen-decompositions (as in Kernel PCA) or matrix inversions (as in Nyström approximations), they propose:
- Subsampling $n$ points from a large dataset of $N$ points.
- Building a small $n \times n$ Gram matrix $K$.
- Multiplying it by a random Gaussian matrix $Z \in \mathbb{R}^{d \times n}$ to create a sketch $ZK$.
- Using this sketch as a projection operator to map all $N$ original points into a low-dimensional space $\mathbb{R}^d$.
The core theoretical contribution is proving that this operation corresponds to a random operator $\Theta$ in the RKHS that preserves a weighted inner product of the form $\langle f, g \rangle_\Sigma = \langle f, \Sigma^3 g \rangle_\mathcal{H}$, where $\Sigma$ is the covariance operator of the data.
Datasets
The authors evaluated their approach on three real-world datasets from the UCI repository:
- Avila Bible: 20,867 samples, 10 dimensions, 12 clusters (scribes).
- IoT (Traffic Traces): 40,000 samples, 115 dimensions, 5 clusters (devices).
- Bank Notes: 1,372 samples, 4 dimensions, 2 clusters (forged vs. genuine).
Key Insights and Ideas
- The $\Sigma^3$ Connection: A surprising finding is that Gaussian sketching doesn't preserve the standard RKHS inner product, but rather one weighted by the cube of the covariance operator ($\Sigma^3$). This happens because the sketching process involves both the sampling of data points and the random Gaussian weights.
- Cheaper than Nyström: While the Nyström method is a standard way to approximate kernels, it requires computing a pseudo-inverse ($O(n^3)$ or $O(dn^2)$ with high constants). K-JL requires only matrix multiplication ($d \cdot n^2$), making it significantly faster to preprocess.
- Preserving Separation: The authors show that if data is "clusterable" or "separable" in the high-dimensional feature space (the typical assumption for Kernel PCA), it remains separable after the K-JL projection, despite the $\Sigma^3$ weighting.
- Stability: Empirically, K-JL appeared more stable in terms of clustering performance (Rand Index) compared to fast implementations of KPCA, which can be sensitive to the stability of eigensolvers.
Key Results
- Theoretical Convergence: The authors proved that the sketched inner products converge to the Hilbert space counterparts at a rate of $O(n^{-1/2} + d^{-1/2})$.
- Clustering Performance: On the IoT dataset, K-JL achieved a Rand Index of 0.749, nearly identical to KPCA (0.759) and K-k-means (0.745).
- Speed: K-JL was consistently the fastest method. For the IoT dataset, K-JL took 0.447s for preprocessing, compared to 0.537s for K-k-means and 0.500s for KPCA. On smaller datasets like Bank Notes, it was up to 3x faster than K-k-means.
- Dimension Efficiency: The experiments showed that a very small projection dimension (e.g., $d=100$) is often sufficient even for datasets with tens of thousands of points.
Limitations and Future Work
- Effective Dimension: The theoretical bounds depend on the "effective dimension" ($s_\Sigma$) of the data. If the kernel's eigenvalues decay very slowly (i.e., the data is truly high-dimensional in the RKHS), the required $n$ and $d$ might need to be larger to maintain accuracy.
- Centralization: The current analysis focuses on "centralized" versions of the algorithms. Extending this to uncentralized data or different types of sketching matrices (like CountSketch) remains an open area.
- Choice of $n$: The results are sensitive to the subsample size $n$. While $n \ll N$ works, choosing the optimal $n$ for a specific level of distortion is still a heuristic process in practice.
Summary updated