I am planning to use the Nystroem method to approximate a Gram matrix induced by any kernel function. I found the Nystroem implementation in scikit-learn.

As far as I understood, the full Gram Matrix should be estimated. Let have $x_1, \ldots, x_n$ as data points where $x_i \in \mathbb{R}^d$ for all $i = 1 \ldots n$. My goal is to build a Kernel Matrix containing each pair $k(x_i, x_j)$. Then the output should be $\tilde{G} \in \mathbb{R}^{n \times n}.$ The scikit-learn implementation, however, returns $\tilde{G} \in \mathbb{R}^{n \times m}$ where $m$ is the number of components the user has given for the lower-rank approximation.

How can the full Gram/Kernel Matrix be approximated using scikit-learn?

# imports
from sklearn.kernel_approximation import Nystroem
from sklearn.gaussian_process.kernels import RBF
# creating data
x = np.random.normal(size=(100, 2))

# accurate kernel function
kernel = RBF()
gram_matrix = kernel(x)
# approximated kernel function
m = 50
kernel_approx = Nystroem(kernel, n_components=m)
gram_matrix_approx = kernel_approx.fit_transform(x)
if gram_matrix.shape == gram_matrix_approx.shape:

The shapes are always different. Why?


1 Answer 1


Sklearn's Nystroem does not compute the Gram matrix itself, it returns the Feature map $\Phi$. The exact kernel matrix is approximated by $\tilde{G} = \Phi \Phi^\top$. Your code should look like this:

kernel_approx = Nystroem(kernel, n_components=m)
feature_matrix = kernel_approx.fit_transform(x)
gram_matrix_approx = feature_matrix @ feature_matrix.T

And then

if gram_matrix.shape == gram_matrix_approx.shape:

would print what you expect.

You can check how good an approximation you got by visually comparing

import matplotlib.pyplot as plt

If you do want the $n \times n$ Gram matrix, it will take $\mathcal{O}(n^2)$ time if you compute it directly, and $\mathcal{O}(n^2 m)$ time if you first compute the Nystroem approximation and then evaluate $\Phi \Phi^\top$, so computing it directly would be faster.

  • 1
    $\begingroup$ I have actually implemented the Nystroem Method by myself now. It is marginally faster than computing it directly. As I understood, the singular value decomposition which was done by scikit-learn is not necessary and only needed for the proof or not? And if the approximation has a worse running time complexity (by your statement), why is it used anyways? $\endgroup$ Commented Jul 10, 2020 at 19:56
  • $\begingroup$ When you actually want to apply it in kernel methods, the low-rank approximation $\Phi \Phi^\top$ can significantly speed up computation - details depend on the algorithm, but you never compute the product $\Phi \Phi^\top$ directly, instead you compute matrix-vector products $\Phi (\Phi^\top v)$. $\endgroup$
    – STJ
    Commented Jul 11, 2020 at 20:39
  • $\begingroup$ @ManhKhôiDuong did my answer actually answer your question? if so it'd be nice if you could accept it, if not I'd be happy to clarify, just let me know! :) $\endgroup$
    – STJ
    Commented Jul 13, 2020 at 16:31
  • $\begingroup$ @STJ do you have any insight on a similar question on SO? If so, I have a bounty right now for 400 points going. Need some help with this problem stackoverflow.com/questions/78486471/… $\endgroup$
    – O.rka
    Commented May 19 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.