6
$\begingroup$

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of the edges on the hypercube could be different for different dimensions. The hypercube basically is a hyper-rectangle. Now the questions are the following: 1. Given the dimension of the hyper-rectangle, what is the lower bound of the distortion to the original metric space? 2. How to achieve that, i.e., the lengths of the edges, the vertices for each point? 3. Is the optimal embedding P or NP?

$A = (P,C), |P| = N, C\in [0,1]^{N\times N}$, find a mapping $f:P \rightarrow \times_{j=1}^D $ { $0,l_j $ }, $l_j > 0$.

such that for any $\frac{1}{\mu} C_{ij} \le |f(P_i)-f(P_j)| \le \mu C_{ij} $,

where $\mu \sim \Omega(g(D,N))$, is a polynomial function. Thanks a lot!

$\endgroup$
3
  • $\begingroup$ I guess you know Kuratowski embedding, it gives a natural way to map your space to N-dimensional "hyper-rectangle" (see en.wikipedia.org/wiki/Kuratowski_embedding) $\endgroup$ Jan 8, 2010 at 21:27
  • $\begingroup$ Perhaps this paper of Ron Graham and Peter Winkler would be helpful: pnas.org/content/81/22/7259.full.pdf $\endgroup$ Jan 8, 2010 at 21:37
  • $\begingroup$ Thanks for both of you. But my problem is that I don't really embed to a $\ell_1$ space. They have to be the vertices of the hyper-rectangle. $\endgroup$ Jan 9, 2010 at 4:31

3 Answers 3

3
$\begingroup$

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, c\mu^{-1}, c\mu^{-2}, \dots, c\mu^{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 $c\mu^{-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(2\ln 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.

$\endgroup$
1
  • $\begingroup$ randomized algorithm is already good enough. Thanks! $\endgroup$ Apr 15, 2010 at 16:00
11
$\begingroup$

This is a well studied (and alas hard) problem. since you're allowing the hypercube to have arbitrary weights, it seems like you're really embedding into an $\ell_1$ space. in general, for such spaces, you can get a $\log n$ distortion using $\log^2 n$ dimensions, and this is tight (the shortest path metric for an expander graph is a lower bound). There's a ton of work on this topic in the area called 'metric embeddings'. a good place to start is the 2004 survey by Indyk and Matousek here, and Tim Roughgarden has good class notes (and references)

The problem is NP-hard for $\ell_1$ in general.

$\endgroup$
3
  • $\begingroup$ This is a fairly educating answer. I appreciate it. But the thing here is that I have to restrict the assignment of points to the vertices instead of any vector inside the hypercube. So it isn't really embedding to $\ell_1$ space. Or, maybe you could show me how to move those points to the vertices after embedding without much distortion, that would be cool. $\endgroup$ Jan 9, 2010 at 4:28
  • 1
    $\begingroup$ The usual way to convert l_1 to a hamming space is by writing the coordinates in unary and then concatenating them. This is potentially nasty if the values are large. Generally this can be fixed if the value ranges aren't large by scaling, but I'm also convinced there's a direct embedding into the hypercube that I can't find a ref for. $\endgroup$ Jan 9, 2010 at 4:52
  • $\begingroup$ If, by any chance, you find the ref, please do let me know. I kinda like the idea of converting l_1 to a hamming space by concatenation. Thanks. $\endgroup$ Jan 9, 2010 at 5:04
0
$\begingroup$

Perhaps I'm not following what you're asking perfectly, but if you have $N$ points, and a distance matrix which is $N \times N$ in size, you could use an $N$-dimensional hypercube.

This hypercube would have the $N$ points at the $N$ vertices defined by the vectors $P_1=(1,0,...,0)$, $P_2=(0,1,0,...,0)$, ..., $P_N=(0,0,...,0,1)$. Thus the $N$ points all exist at Hamming distance $=1$ from the origin (0,0,...,0). In this embedding, all of the $N$ points are at the vertices of the $N$-dimenional unit hypercube. In the unit hypercube embedding, the Hamming distance is between each pair of points is $2$, and the Minkowski distance between each pair of points if $\sqrt(2)$

The pair-wise distances which you already have as a given are used to define the length of the distance between two vertices and thus give the separation between each pair of points. Of course, if the distances are not in a Euclidean space, you can't use a Minkowski metric to define the distances.

If you want to have this be a euclidean space, then you can use different techniques to get the appropriate desired pair-wise Euclidean distance,

$$d_{a,b}={(\sum_{i=1}^{i=N}} (a_i-b_i)^2) ^{0.5}$$

or you can use whatever other metric may be appropriate in your case.

For the euclidean distance, you can set each point to be at a distance $d_n, 1 \le n \le N$, then calculate the pairwise distances for all of the data points and try to move the points around in order to get closer to approximating your original distance metric.

Thus now you would have each point $P_n, 1\le n \le N$ at $(v_1,v_2,...,v_N)$ where $v_i=0$ for $i \ne n$, and $v_i=d_i$ for $i=n$. This embedding now places each of the points at a vertex of a hyper-rectangle in $N$-dimensional space, rather than in the unit hypercube.

You could use an annealing method or a genetic algorithm with multiple candidates to mutate and cross over, or try to move one point at a time to optimize that point's pair-wise distance to all of the other points.

What is the order of magnitude of your data set's $N$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.