Memory Efficient Kernel Approximation(MEKA)


DESCRIPTION

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.


CITATION

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].


Download

You can download the code here.


Usage

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)


>>demo_ijcnn
***************************
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.