Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$). Imagine I have a source that outputs a point by choosing among the $n$ points according to the probability distribution $p_1,\dots,p_n$. Also, I have a distance measure $D(\cdot,\cdot)$ so that $D(x,y)$ is the dissimilarity between two points $x,y$.

I want to design a codebook $y_1,\dots,y_m \in \mathcal{S}$ that provides low-distortion encoding for this source, where $m$ is given and $m<n$. The point $x_i$ will be mapped to the $y_j$ that is most similar to $x$; then I'll transmit $y_j$ instead of $x_i$. This incurs distortion $D(x_i,y_j)$. Let $f(\cdot)$ be the function that maps $i$ to $j$, i.e., $y_{f(i)}$ is the $y$-point that is nearest to $x_i$. The expected distortion of a codebook is $$\sum_{i=1}^n p_i \cdot D(x_i,y_{f(i)}).$$ Given the $x_i$'s, $p_i$'s, and $m$, I want to find a codebook $y_1,\dots,y_m$ whose distortion is as small as possible.

Equivalently, this can be phrased as a clustering problem. I'm given $m$, and I want to cluster the points $x_1,\dots,x_n$ into $m$ clusters, with one centroid for each cluster, such that the expected distance from each point to the centroid of the cluster containing it is as small as possible. (This expected distance is computed by taking a weighted average over all the points $x_i$, weighted by the probabilities $p_i$.)

Are there any reasonable algorithms for this? This reminds me of clustering, but I've never seen clustering algorithms that take into account probabilities $p_1,\dots,p_n$. Alternatively, this reminds me of vector quantization, but the methods I've seen for vector quantization all focus on the $L_2$ distance metric (i.e., $D(x,y)=\|x-y\|_2$), and here I have a different distance measure -- in fact, it's not even a metric. Those methods don't seem to generalize in any clear way to an alternative distance measure. I do have $D(s,t) \ge 0$ and $D(s,t)=D(t,s)$ and $D(s,s)$ for all $s,t$.

  • $\begingroup$ From what larger universe are the $y_j$ chosen? (Is it the same $n$-point set, implying that each $y_j$ is equal to some $x_i$?) Also you say that $D(x, y)$ is not a metric; does it have any properties at all (e.g. is $D(x, x) = 0$, and is $D(x, y) = D(y, x)$ for all $x, y$?) $\endgroup$ – j_random_hacker Jul 22 '16 at 15:07
  • $\begingroup$ If the $y_j$ are chosen from the same $n$-point set as the $x_i$ are, and if $D(x, y)$ obeys $D(x, x) = 0$ but allows $D(x, y) \ne D(y, x)$, then I think I have a reduction from Set Cover... Maybe this can be extended to handle a symmetric $D$, but I'll wait for more details. Also: this reduction makes no use of $p_i$ at all, so it would hold for other kinds of clustering. $\endgroup$ – j_random_hacker Jul 22 '16 at 15:18
  • $\begingroup$ Thanks for the comments, @j_random_hacker! I updated the question. Yes, it has those properties. I am imagining that the $x_i$'s come from a larger space $\mathcal{S}$, and the $y_j$'s can come from that space too, so there's no requirement that the $y_j$'s be selected as a subset of $x_i$'s. In general I do fully expect this to be NP-hard, as clustering with a general metric is NP-hard too (I think), but I was hoping for some techniques that will typically work pretty well (as we have in the clustering literature). $\endgroup$ – D.W. Jul 22 '16 at 17:24
  • $\begingroup$ If the $y_j$ come from a continuous space then "unfortunately" my reduction probably won't work. OTOH it seems that your $D$ is also continuous (since otherwise you'd obviously have an uncountable number of points to individually test) -- that doesn't help me, but might help someone else. On the third and final hand, there seem to be similarities to the facility location problem from OR, though some quick googling didn't get me a simple and definitive description of "the" facility location problem. $\endgroup$ – j_random_hacker Jul 23 '16 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.