11
$\begingroup$

Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$. Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to final distance: $$ \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \}$$

There are other measures of quality though: Dhamdhere et al study the "average" distortion: $$ \sigma = \frac{\sum d(x,y)}{\sum f(\mu(x), \mu(y))}.$$

However, the measure I'm interested in here is the one used by MDS-like methods, which looks at the average additive error: $$ \varepsilon^2 = \sum | d(x,y) - f(\mu(x), \mu(y))|^2$$

Although MDS-like methods are studied extensively outside the theoryCS community, I'm aware of only one paper (by Dhamdhere et al) that examines optimization under this measure, and that too for the limited problem of embedding onto the line ($Y = \mathbb{R}$) (side note: Tasos Sidiropoulos' 2005 MS thesis has a nice review of earlier work)

Is there any more recent work that people are aware of regarding rigorous quality analysis under this notion of error ? While these problems are generally NP-hard, what I'm more interested in are approximations of any kind.

Improve this question
$\endgroup$
3
$\begingroup$

This is a nice question. I don't know of approximation algorithms, but the known hardness results for approximating minimum distortion (and related problems such as metric labeling) should also show that $\epsilon^2$ is hard to approximate.

The reason is that they give a reduction from an NP-hard problem such that in the YES case the distortion is $O(1)$ and in the NO case the distortion is $\Omega(k)$ for at least a constant fraction of the edges. Hence, in the YES case $\epsilon^2$ will be a factor $k$ smaller than in the NO case. For details, see for instance the paper by Khot-Saket: www.cs.cmu.edu/~rsaket/pubs/approx.pdf

I'm not exactly sure which hardness factor follows from their paper, but it shouldn't be difficult to figure out. (I would guess at least the $\log^c(n)$ factor that you get for metric labeling should follow.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ that's a good suggestion. I'll definitely look into the metric labelling work. It's known that even embedding onto the line is MAX SNP-hard, but it would be interesting (albeit disappointing) to see stronger results. $\endgroup$ – Suresh Venkat Sep 10 '10 at 16:11
2
$\begingroup$

I might be missing something, but why is $\epsilon^2 \le (\rho-1)\sum d(x,y)^2$? We're interested in additively approximating, so we cannot scale to make $f(\mu(x), \mu(y)) \ge d(x,y)$ for all $x,y$, right?

One advantage here is that we can do badly on short lengths and be OK ultimately. Also, is the problem easy (to approximate, even) if, say we want to embed into $\ell_2$? (can we write a mathematical program to capture the question?)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good point. I changed my answer. $\endgroup$ – Moritz Sep 11 '10 at 21:20
  • $\begingroup$ it depends on the formulation. If you pose the problem as minimizing $\epsilon$ for a fixed-dimensional target subspace, then the rank constraints cause some problems. If you use the "JL-style" formulation (ie fix the error and find the right dimensionality), then something might be doable. $\endgroup$ – Suresh Venkat Sep 12 '10 at 22:18
  • $\begingroup$ A quantity which may be useful to "compete against" is $S:= \sum d(x,y)^2$. Consider the problem of embedding into $\ell_1$ (I suggested $\ell_2$ earlier, but it has the messy sqrt). We must clearly aim to obtain embeddings which have $\epsilon^2$ being $o(S)$ (in a vague sense, this means we are $(1+o(1))$ off multiplicatively for most $x,y$. Can we obtain such an embedding for, say (const degree) expanders? (or prove it isn't possible?) $\endgroup$ – aditya Sep 16 '10 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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