Memory Efficient Kernel Approximation(MEKA)


MEKA is a memory efficient and fast kernel approximation method. It is well-suited to form the low-rank approximation for large-scale kernel matrices.
It is written in matlab and a mex wrapper for fast k-means.


You are welcome to use the code, however please acknowledge its use with a citation:

Memory Efficient Kernel Approximation, S. Si, C.-J. Hsieh, and I.S. Dhillon, ICML 2014.
[PDF] [Slides].


You can download the code here.


function [U,S] = meka(A,k,gamma,opts)
% [U,S] = meka(A, k, gamma,opts)
% K \approx U*S*U^T
% Arguments:
% A an n by d sparse matrix(each row is a data point)
% k the target rank
% gamma the kernel width in RBF kernel
% opts.noc number of clusters(default 10)
% opts.eta the percentage of blocks to be set to be 0(default 0.1)

Example on ijcnn dataset (49990 samples)

Parameters ...
Rank = 500          gamma= 1.000000
# of clusters = 10 eta= 0.100000
Begin meka!
The time for kmeans 0.160000
The time for approximating diagonal blocks 1.600000
The time for approximating off-diagonal blocks is 0.820000
Done with meka!
The total time cost for meka is 3.310000 secs
Testing meka!
The relative approximation error is 0.040114

Bug reports and comments are always appreciated. We would like to know who showed interest in our work, feel free to contact us.