# Optimal binary code for points in a metric+probability space

Does anyone know of any results on this topic?

Basically I'm considering this problem. You have some space $X$ from which you can draw points $x$ and $y$, a distance metric $d(x,y)$, and a sigma-algebra/probability measure on $X$. Maybe $X$ is ${\bf R}^n$ and you have a pdf $p(x)$, that's actually probably general enough for me.

Now the problem is you want to make an encoding function $f: X \to {0,1}N$ and a decoding function $g: {0,1}N$ such that the expected value of $d(x,f(g(x))$ is minimized. (Or possibly some non-decreasing function thereof, like $d(x(x,f(g(x))^2 )$ The basic idea is that $f$ is a function that maps from a point in your space to a fixed-length binary code. $g$ is a function that maps from a binary code vector to a point in your space. You want to find a code such that the loss of the compression is smallest.

It's a lot like PCA, but the code elements are binary, and the encoder/decoder functions are unrestricted.

One thing I've thought of so far is that this reduces to the problem of picking $2N$ points $P$ in $X$ such that the expected distance from $x$ to the nearest point in $P$ is minimized.

If anyone knows of any work on this kind of problem, I'd be very interested to read about it. I don't necessarily need a procedure for coming up with the optimal code or anything like that. I imagine someone must have derived some properties that the optimal code should have though.

• Please proof read your question. What is the source/target of $g$? Do you really mean $f(g(x))$ or is it $g(f(x))$? Finally, you can and should use TeX. Nov 12 '10 at 18:38
• I've added TeX but wasn't able to guess what you meant by $f:X\to0,1N$ or $g:0,1N$. If you can't do Tex, then write it out in words, please. Nov 12 '10 at 21:40
• Gerry, 0,1N probably is $\{0,1\}^N$. I can probably try and guess the rest but it's his problem, not mine. Nov 13 '10 at 0:30

The problem you're trying to solve is a generalization of what is called the 'continuous $k$-median problem'. In that problem, the center locations are arbitrary, whereas in your case, they are on a grid. However, your problem starts with an arbitrary metric space. While the cited problem is NP-hard, and is likely to remain so for your problem, there are useful heuristics that you can try for the case when $X = {\mathbb R}^n$, including $k$-means-style methods.