0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Manh Khôi Duong Jul 10 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 Jul 11 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 Jul 13 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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