mg.metric geometry - How can I embed an N-points metric space to a hypercube with low distortion?

Y. Bartal has studied a related problem of embedding metric spaces to hierarchically separated trees. With $1 < mu$ being a fixed real number, a $mu$-HST is equivalent to the set of corners of a rectangle whose edges are of length $c, cmu^{-1}, cmu^{-2}, dots, cmu^{1-D}$ with the $l_infty$-metric. That is, if you think of the space as the set of bit sequences of length $D$, the distance of two sequences is $cmu^{-j}$ if they first differ in bit $j$.

Now in your question you didn't ask for $infty$-metric, but for this set of points, it doesn't really matter which metric you take because the distortion between this and either the $l_1$ or $l_2$ metric is bounded by a constant (if you fix $mu$ but $D$ can vary).

(This metric can be considered a graph metric on a special tree, that is, one where the points are some (but not necessarily all) vertexes of a tree graph with weighted edges, and the distance is the shortest path. This is where "tree" in the name comes from.)

Now Bartal's result in [1] basically says that you can embed any metric space randomly to a $mu$-HST with distortion at most $mu(2ln n+2)(1+log_mu n)$ where $n$ is the number of points. (Also, this embedding can be computed with a randomized polynomial algorithm.)

For this, you need to know what a distortion $alpha$ random embedding $f$ means. It means that for any two points $d(x,y) < d(f(x),f(y))$ is always true and that the expected value of $d(f(x),f(y))$ is at most $alpha d(x,y)$. For many applications, this is just as good as a deterministic embedding with low distortion. In fact, you can make a deterministic embedding with low distortion from it by imagining the metric $d^* $ on the original space where $d^*(x,y) = E(d(f(x), f(y))$, but this notion isn't too useful because the resulting metric does not have nice properties anymore (it's not HST). Indeed, I believe the randomness is essential here as I seem to remember reading somewhere that you can't embed a cycle graph (with equal edge weights) to a tree graph with low distortion.

Anyway, this might not really answer your question. Firstly, $D$ (the number of dimensions of the rectangle) is not determined in advance, but that's not a real problem because if you have $D$ significantly different distances in the input metric then you need at least that large a $D$ for any embedding; and with this embedding you don't need a $D$ larger than $log_mu (Delta/delta)$ where $Delta$ and $delta$ are the largest and smallest distances in the input. The real problem is that you seem to want to know a deterministic embedding, and the highest possible distortion necessary in that case, which this really doesn't tell. For example, a cycle graph with an even number $n$ of vertexes can of course be embedded isometrically to a cube of dimension $n/2$.

Survey [2] has some more references.

[1]: Yair Bartal, On Approximating Arbitrary Metrics by Tree Metrics. Annual ACM Symposium on Foundations of Computer Science, 37 (1996), 184–193.

[2]: Piotr Indyk, Jiří Matoušek, Low-distortion embeddings of finite metric spaces. Chapter 8 in Handbook of Discrete and Computational Geometry, ed. Jacob E. Goodman and Joseph O'Rourke, CRC Press, 2004.