Lecture Notes for Computer Science (DAGM), 2010

###
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