Does anyone know of any results on this topic?
Basically I'm considering this problem. You have some space X $X$ from which you can draw points x $x$ and y, $y$, a distance metric d(x,y), $d(x,y)$, and a sigma-algebra/probability measure on X. $X$. Maybe X $X$ is Rn ${\bf R}^n$ and you have a pdf p(x), $p(x)$, that's actually probably general enough for me.
Now the problem is you want to make an encoding function f: $f: X -> \to {0,1}N 0,1}N$ and a decoding function g: $g: {0,1}N 0,1}N$ such that the expected value of d(x,f(g(x)) $d(x,f(g(x))$ is minimized. (Or possibly some non-decreasing function thereof, like d(x(x,f(g(x))2 $d(x(x,f(g(x))^2 )$ The basic idea is that f $f$ is a function that maps from a point in your space to a fixed-length binary code. g $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 $2N$ points P $P$ in X $X$ such that the expected distance from x $x$ to the nearest point in P $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.
