Average distortion embeddings

Question

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.

Answer 1

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.)

Answer 2

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?)