RandFeat: Random Fourier Approximations for Skewed Multiplicative Histogram Kernels
Fuxin Li, Catalin Ionescu and Cristian Sminchisescu

This is our implementation of RandFeat. It includes a number of other methods of approximation for different kernels and allows one to compare among them. It includes the following kernels:

Kernel Type Formula Approximation
Gaussian multiplicative $exp(-kparam*||x-y||^2)$ Monte Carlo [Rahimi and Recht 2007]
Laplacian multiplicative $exp(-kparam*||x-y||)$ Monte Carlo [Rahimi and Recht 2007]
Intersection additive $\sum_i\max(|x_i||y_i|)$ Signal Theoretic [Vedaldi and Zisserman 2010]
$1 - \chi^2$ additive $\sum_i\frac Signal Theoretic [Vedaldi and Zisserman 2010]
skewed $\chi^2$ multiplicative $\prod_i \frac Monte Carlo [Li, Ionescu and Sminchisescu 2010]
Package

The system has been tested on MATLAB 7.9 and 7.10 on a Linux 64-bit machine with 8 Gb of memory. For details see the README file in the package below. This package is free for academic use only. No warranty.

Performance

Error on approximation of a HOG kernel with 1700 input dimension:

Classification performance with the bow_features.mat (in the package) extracted from PASCAL VOC‘09 training set.

>> DEMO_classification 
Training model with linear kernel.
Accuracy = 33.1043% (530/1601)
Training model with random Fourier features on additive chi-square kernel.
Accuracy = 59.4628% (952/1601)
Training model with random Fourier features on Gaussian kernel.
Accuracy = 60.6496% (971/1601)
Training model with random Fourier features on Laplacian kernel.
Accuracy = 61.8364% (990/1601)
Training model with random Fourier features on skewed chi-square kernel.
Accuracy = 64.5222% (1033/1601)

Please reference this package as:

@misc{randfeat-release1, 
author = "Fuxin Li, Catalin Ionescu, Cristian Sminchisescu", 
title = "RandFeat: Random Fourier Approximations for Skewed Multiplicative Histogram Kernels, Release 1", 
howpublished = "http://sminchisescu.ins.uni-bonn.de/code/randfeat/randfeat-release1.tar.gz"}

Reference

[58] Random {F}ourier Approximations for Skewed Multiplicative Histogram Kernels
Fuxin Li and Catalin Ionescu and Cristian Sminchisescu

Lecture Notes for Computer Science (DAGM), 2010

Code