# Kernel approximation with Nystroem method and usage in scikit-learn

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:
print('True')
else:
print('False')


The shapes are always different. Why?

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:
print('True')
else:
print('False')


would print what you expect.

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

import matplotlib.pyplot as plt
plt.matshow(gram_matrix)
plt.matshow(gram_matrix_approx)
plt.show()


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.

• 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? Commented Jul 10, 2020 at 19:56
• 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)$.
– STJ
Commented Jul 11, 2020 at 20:39
• @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! :)
– STJ
Commented Jul 13, 2020 at 16:31
• @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/… Commented May 19 at 6:14