# Pyramid Match Kernel: How to fit grid around data points?

I am planning to use Pyramid Match Kernel method for object recognition from depth images: I am going to extract a set of feature vectors $x \in \mathbb{R}^d$ for each object instance and then I want to use the Pyramid Match Kernel as described in http://jmlr.csail.mit.edu/papers/volume8/grauman07a/grauman07a.pdf in Grauman's paper, in order to use the set of feature vectors for each object with a SVM classifier.

I have a problem to understand how exactly we are supposed to build bins around the data points to begin with. The paper gives the following definition:

What does "inter-vector" distance mean here? I think of the following: We consider all $x_i$ values for each $X$ in $S$. Then we find two vectors with smallest distance $d$ ,(unique ones) and then scale all vectors with $1/d$. Then $D$ is the maximum absolute value of a vector element in $S$.

Is this what the authors meant here? What about if we are going to test a new vector $y$, how should we scale it?

No, that's not it. Look at the last sentence of your quote:

... which may be enforced by scaling the data to some precision and truncating to integer values.

So this is exactly what you do. Take all your feature vectors, multiply them by 1000 (or some other factor), and truncate to integer. Then the distance between any two unique feature vectors will have to be >= 1. If you have a new vector y, then you multiply it by the same factor and truncate.

• Why are we truncating to integer and how does this guarantees that the distance between data vectors is larger than 1? I did not understand this, can you elaborate a bit more? Nov 6, 2014 at 17:29
• Think about it: if you have a set of points, and all points have integer coordinates, then no two points can have a distance less than 1, unless they are the same point.
– Dima
Nov 6, 2014 at 19:02