Średnie osadzenia zniekształceń

11

Rozważmy dwie przestrzenie metrycznych i i z obszaru wstawiania . Tradycyjne osadzanie przestrzeni metrycznej mierzy jakość jako najgorszy stosunek pierwotnej odległości do odległości końcowej: $(X, d)$ $(Y, f)$ $\mu : X \rightarrow Y$ $\mu$

ρ = max_{p, q \in X} {\frac{d (x, y)}{f (μ (x), μ (y))}, \frac{f (μ (x), μ (y))}{d (x, y)}}

$\rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \}$

Istnieją jednak inne miary jakości: Dhamdhere i wsp. Badają „średnie” zniekształcenie:

σ = \frac{\sum d (x, y)}{\sum f (μ (x), μ (y))} .

$\sigma = \frac{\sum d(x,y)}{\sum f(\mu(x), \mu(y))}.$

Jednak miarą, która mnie tutaj interesuje, jest metoda stosowana przez metody podobne do MDS, która analizuje średni błąd addytywności :

ε^{2} = \sum | d (x, y) - f (μ (x), μ (y)) |^{2}

$\varepsilon^2 = \sum | d(x,y) - f(\mu(x), \mu(y))|^2$

Chociaż metody podobne do MDS są szeroko badane poza społecznością teorii CS, jestem świadomy tylko jednego artykułu ( autorstwa Dhamdhere i in. ), Który analizuje optymalizację w ramach tej miary, a także w odniesieniu do ograniczonego problemu osadzania na linii ( ) (uwaga dodatkowa: praca dyplomowa MS Tasos Sidiropoulos z 2005 r. ma ładny przegląd wcześniejszych prac) $Y = \mathbb{R}$

Czy są jakieś najnowsze prace, które ludzie są świadomi w związku z rygorystyczną analizą jakości pod tym pojęciem błędu? Chociaż problemy te są na ogół trudne dla NP, bardziej interesują mnie przybliżenia dowolnego rodzaju.

approximation-algorithms cg.comp-geom embeddings

— Suresh Venkat
źródło

3

$\epsilon^2$

$O(1)$ $\Omega(k)$ $\epsilon^2$ $k$

$\log^c(n)$

— Moritz
źródło

to dobra sugestia. Zdecydowanie przyjrzę się metrykalnemu etykietowaniu. Wiadomo, że nawet osadzenie na linii jest trudne w SNP, ale byłoby interesujące (choć rozczarowujące), aby zobaczyć lepsze wyniki.

— Suresh Venkat,

2

$\epsilon^2 \le (\rho-1)\sum d(x,y)^2$ $f(\mu(x), \mu(y)) \ge d(x,y)$ $x,y$

$\ell_2$

— aditya
źródło

Słuszna uwaga. Zmieniłem odpowiedź.

— Moritz

ϵ

$\epsilon$

S := \sum d (x, y)^{2}

$S:= \sum d(x,y)^2$

ℓ_{1}

$\ell_1$

ℓ_{2}

$\ell_2$

ϵ^{2}

$\epsilon^2$

o (S)

$o(S)$

(1 + o (1))

$(1+o(1))$

x, y

$x,y$ . Czy możemy uzyskać takie osadzenie, powiedzmy (const stop) ekspanderów? (lub udowodnić, że nie jest to możliwe?)

— aditya