Title: Improve Execution Time of MATLAB Function
Tags: matlab;time;execution
Question: The following function calculates the Gaussian Kernel and is part of the Kernel Ridge Regression algorithm that I wrote. I was wondering how could I modify this function properly in order to improve the execution time (i.e. get rid of the two for loops). Any ideas?
function [K] = calculate_krr_gaussiankernel(Xi,Xj,S)
K = zeros(size(Xi,1),size(Xj,1));
for Ixi = 1:size(Xi,1),
for Ixj = 1:size(Xj,1),
K(Ixi,Ixj) = exp((-norm(Xi(Ixi,:) - Xj(Ixj,:)) .^ 2) ./ (2 * (S .^ 2)));
end
end
EDIT: The formula:


Here is another answer: You can certainly double the speed (approximately) since K is symmetric.  In addition you can calculate the norm of the difference vector and then make a single call to exp() which may be faster than calling exp() over and over again.  Putting this together:
function [K] = calculate_krr_gaussiankernel(Xi,Xj,S)
arg = zeros(size(Xi,1),size(Xj,1));
for Ixi = 1:size(Xi,1),
% diagonal elements can be done in outer loop:
arg(Ixi,Ixi) = norm(Xi(Ixi,:) - Xj(Ixi,:));
for Ixj = Ixi+1:size(Xj,1), % off-diagonals done once and copied
arg(Ixi,Ixj) = norm(Xi(Ixi,:) - Xj(Ixj,:));
arg(Ixj,Ixi) = arg(Ixi,Ixj);
end
end
K = exp(( -arg.^ 2) ./ (2 * (S .^ 2)))

Here is another answer: Here's a version that's most likely faster. It might however give rise to memory issues for large Xi/Xj.
function K = calculate_krr_gaussiankernel(Xi, Xj, S)
%# create an array of difference between Xi(r,:) and Xj(s,:) for all r,s
delta = bsxfun(@minus, permute(Xi,[1 3 2]), permute(Xj,[3 1 2]));
%# calculate the squared norm
ssq = sum(delta.^2, 3);
%# calculate the kernel
K = exp(-ssq./(2*S.^2));
Here's an explanation of what I'm doing:
the bsxfun line: I reshape the inputs, such that I can get, at every (i,j), the difference vector in the third dimension
the ssq line simply takes the sum of squares. I could take the square root here and thus get the norm, but since we'll square that again, anyway, there's no point in that.
the final line implements the formula in the OP, where ssq is the squared norm of the differences.
Comment for this answer: @RodyOldenhuis: Thanks for the clarification!
Comment for this answer: @eualin: I have added an explanation of the individual steps.

{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 2, 'CommentCount': 0, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2012:00:08/15/12', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<matlab><time><execution>', 'Title': 'Improve Execution Time of MATLAB Function', 'ViewCount': 357, 'id': 11978152, 'user_AboutMe': '', 'user_AccountId': 363226.0, 'user_DisplayName': 'user706838', 'user_Reputation': 4922.0, 'user_Views': 426.0, 'user_id': 706838.0}}