Approximate RBF kernel's infinite feature space

Hello,

I'm trying to solve an integral in RBF Kernel's feature space. It is known that the feature space of the RBF kernel has an infinite number of dimensions. Is there a Matlab code that constructs an approximate mapping for the RBF kernel ? Technically, it would map a point from function space of dimension m to another feature space with dimension n, that approximates the infinite feature space dimension of the kernel.

Thank you

Answer 1

[Ayush Anand]

Hi Khalil,

I understand you want to know if there is a way to approximately map RBF kernel from its default infinite dimensional space to a lower dimensional space. You can do this using the Nystrom approximation. The Nystrom method works by sampling a subset of the data and using it to approximate the full kernel matrix.

The Nystrom method approximates the kernel matrix “K” by a low-rank approximation “~K”, using a subset of “m” columns sampled from the original kernel matrix “K” of size “n x n”. The approximation is given by:

where “C” is an “n x m" matrix consisting of the “m” columns of “K” corresponding to the sampled points, and “W” is the "m x m" matrix that is the intersection of the “m” rows and “m” columns of “K” corresponding to the sampled points.

Here is an example MATLAB code that uses the Nyström method to approximate the RBF kernel:

X = randn(1000, 100); % Generate some data: 1000 samples with 100 features each 
gamma = 1; % Parameter for the RBF kernel 
m = 20; % Number of samples for the Nyström approximation 

% Compute the Nyström approximation 
[K_approx, U, Lambda] = nystromRBFApproximation(X, gamma, m); 

function [K_approx, U, Lambda] = nystromRBFApproximation(X, gamma, m) 
% X is the input data matrix (size n x d, with n samples and d features) 
% gamma is the parameter of the RBF kernel exp(-gamma * ||x-y||^2) 
% m is the number of samples to use for the Nyström approximation 

% Step 1: Randomly sample m points from the dataset 
n = size(X, 1); 
idx = randperm(n, m); 
X_sample = X(idx, :); 

% Step 2: Compute the kernel matrix C and W 
C = pdist2(X, X_sample, 'squaredeuclidean'); 
C = exp(-gamma * C); 
W = pdist2(X_sample, X_sample, 'squaredeuclidean'); 
W = exp(-gamma * W); 

% Step 3: Perform eigen-decomposition of W 
[V, Lambda] = eig(W); 
Lambda = diag(Lambda); 
Lambda_inv_sqrt = 1./sqrt(Lambda); 

% Step 4: Compute the approximate kernel matrix K_approx 
K_approx = C * (V * diag(Lambda_inv_sqrt)) * (V' * C'); 

% Step 5: Compute the approximate feature map U 
U = C * (V * diag(Lambda_inv_sqrt)); 

end 

I hope this helps!