<p>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.</p>

<p>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 <em>constant fraction</em> 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</p>

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

CC BY-SA 2.5
2010-09-10T16:11:01.643Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-09-10T16:06:54.043Z
2010-09-11T21:21:53.700Z
2010-09-11T21:21:53.700Z
Moritz
<p>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?</p>

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

CC BY-SA 2.5
2010-09-11T21:20:51.480Z
Good point. I changed my answer.
Moritz
CC BY-SA 2.5
2010-09-12T22:18:59.053Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-09-16T12:49:12.217Z
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?)
aditya
CC BY-SA 2.5
2010-09-11T14:04:08.183Z
2010-09-11T14:04:08.183Z
aditya
<p>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)} \}$$</p>

<p>There are other measures of quality though: <a href="http://www.cs.cmu.edu/~kedar/avgline.ps">Dhamdhere et al</a> study the "average" distortion:
$$ \sigma = \frac{\sum d(x,y)}{\sum f(\mu(x), \mu(y))}.$$</p>

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

<p>Although MDS-like methods are studied extensively outside the theoryCS community, I'm aware of only one paper (<a href="http://www.cs.cmu.edu/~kedar/approx04.ps">by Dhamdhere et al</a>) 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' <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.8039&amp;rep=rep1&amp;type=pdf">2005 MS thesis</a> has a nice review of earlier work)</p>

<p>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. </p>

<approximation-algorithms><cg.comp-geom><embeddings>
Average distortion embeddings
Suresh Venkat
# Average distortion embeddings

(Asked by: username_0 on 2010-09-10)

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](http://www.cs.cmu.edu/~kedar/avgline.ps) 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](http://www.cs.cmu.edu/~kedar/approx04.ps)) 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.8039&rep=rep1&type=pdf) 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.

**Tags:** approximation-algorithms, cg.comp-geom, embeddings

---

## 2 answers

### Answer by username_1 on 2010-09-10. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2010-09-11. Score: 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?)

> **Comments:**
> **username_1**: Good point. I changed my answer.  
> **username_0**: 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.  
> **username_2**: 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?)  

---

