# How to run K-means clustering on data points of varying dimensionality?

I'm trying to aggregate $T$ local image descriptors (i.e. histograms) into a vector, namely, the Fisher Vector as described in this paper by H. Jégou et al., Aggregating local image descriptors into compact codes, to perform image classification. As a first step, the algorithm calls for running K-means to assign each local descriptor $x_t$ to the nearest centroid $\mu_i$ in a bag-of-visual words (BOW) of $K$ words. This is straightforward when every $x_t$ and $\mu_i$ are $d$-dimensional. However, how does one perform K-means when the descriptors have varying dimensionality i.e. $\dim(x_t) \ne \dim(x_s)$ for some $t \ne s$ where $t, s \in 1..T$?

-
Would it make sense to increase the dimensionality of all descriptors to $d=\max(\{\dim(x1),\dim(x2),...,\dim(xT)\})$ by padding with zeroes or resampling? – marcos Apr 9 '12 at 6:39
Further context, the reason why my descriptors are of varying dimensionality is that they are edge-based directional features of different kinds, as opposed to the standard d-dimensional SIFT local descriptors ubiquitously used in image classification. – marcos Apr 9 '12 at 18:33
In order to cluster, you must first define what is "similar". According to your edge-based directional features, can you tell us how two vectors from two different sets of features should be considered similar? If not, this is probably not a valid question. – Memming Apr 9 '12 at 19:00
Memming, thanks for your comment. I'd hope someone would help me define a meaningful similarity measure between different-length image descriptors (to later build a Fisher Vector) as part of the answer – marcos Apr 10 '12 at 4:44