MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Felipe Voloch 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. – Gerry Myerson 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. – Felipe Voloch 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.

For example, you could fix a collection of centers on the grid, compute the Voronoi diagram, integrate your density within each cell to find the "average" location, and then "snap" this location to the nearest grid cell and repeat.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.