Table of Contents
VLFeat include several low-level routines to speedup common mathematical operations used throughout the library. Most are collected in the mathop.h module.
Comparing vectors
mathop.h includes a number of functions to quickly compute distances or similarity of pairs of vector. Applications include clustering and evaluation of SVM-like classifiers.
Use vl_get_vector_comparison_function_f or vl_get_vector_comparison_function_d obtain an approprite function to comprare vectors of floats or doubles, respectively. Such functions are usually optimized (for instance, on X86 platforms they use the SSE vector extension) and are several times faster than a naive implementation. vl_eval_vector_comparison_on_all_pairs_f and vl_eval_vector_comparison_on_all_pairs_d can be used to evaluate the comparison function on all pairs of one or two sequences of vectors.
Let \( \mathbf{x} = (x_1,\dots,x_d) \) and \( \mathbf{y} = (y_1,\dots,y_d) \) be two vectors. The following comparison functions are supported:
| \( l^1 \) | VlDistanceL1 | \( \sum_{i=1}^d |x_i - y_i| \) | l1 distance (squared intersection metric) |
| \( l^2 \) | VlDistanceL2 | \(\sum_{i=1}^d (x_i - y_i)^2\) | Squared Euclidean disance |
| \( \chi^2 \) | VlDistanceChi2 | \(\sum_{i=1}^d \frac{(x_i - y_i)^2}{x_i + y_i}\) | Squared chi-square distance |
| - | VlDistanceHellinger | \(\sum_{i=1}^d (\sqrt{x_i} - \sqrt{y_i})^2\) | Squared Hellinger's distance |
| - | VlDistanceJS | \( \sum_{i=1}^d \left( x_i \log\frac{2x_i}{x_i+y_i} + y_i \log\frac{2y_i}{x_i+y_i} \right) \) | Squared Jensen-Shannon distance |
| \( l^1 \) | VlKernelL1 | \( \sum_{i=1}^d \min\{ x_i, y_i \} \) | intersection kernel |
| \( l^2 \) | VlKernelL2 | \(\sum_{i=1}^d x_iy_i \) | linear kernel |
| \( \chi^2 \) | VlKernelChi2 | \(\sum_{i=1}^d 2 \frac{x_iy_i}{x_i + y_i}\) | chi-square kernel |
| - | VlKernelHellinger | \(\sum_{i=1}^d 2 \sqrt{x_i y_i}\) | Hellinger's kernel (Bhattacharya coefficient) |
| - | VlKernelJS | \( \sum_{i=1}^d \left( \frac{x_i}{2} \log_2\frac{x_i+y_i}{x_i} + \frac{y_i}{2} \log_2\frac{x_i+y_i}{y_i} \right) \) | Jensen-Shannon kernel |
- Remarks
- The definitions have been choosen so that corresponding kernels and distances are related by the equation:
\[ d^2(\mathbf{x},\mathbf{y}) = k(\mathbf{x},\mathbf{x}) +k(\mathbf{y},\mathbf{y}) -k(\mathbf{x},\mathbf{y}) -k(\mathbf{y},\mathbf{x}) \]
This means that each of these distances can be interpreted as a squared distance or metric in the corresponding reproducing kernel Hilbert space. Notice in particular that the \( l^1 \) or Manhattan distance is also a squared distance in this sense.
Fast basic functions operations
In certain algorithm it is useful to quickly compute integer approximation of certain mathematical operations. Presently, VLFeat includes and implementations of:
- Fast single precision atan2: vl_fast_sqrt_f.
- Fast inverse square root: vl_fast_resqrt_f, vl_fast_resqrt_d.
- Fast square root: vl_fast_sqrt_f, vl_fast_sqrt_d.
- Fast integer square root: vl_fast_sqrt_ui16, vl_fast_sqrt_ui32, vl_fast_sqrt_ui64 (see also Fast integer square root algorithm).