MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 improved formatting

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.

1

# 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 Rn 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 -> {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.