Redukcja wymiarów z luzem?

Johnson-Lindenstrauss lemat mówi przybliżeniu że każdy zbiór z n punktów R d , istnieje mapę F : R d → R k , gdzie k = O ( log n / ε 2 ) tak, że dla wszystkich x , y ∈ S : ( 1 - ϵ ) | | f ( x ) - f ( y ) | | $S$$n$$\mathbb{R}^d$$f:\mathbb{R}^d \rightarrow \mathbb{R}^k$$k = O(\log n/\epsilon^2)$$x, y \in S$ Wiadomo, że podobne stwierdzenia nie są możliwe dlametryki ℓ 1 , ale czy wiadomo, czy istnieje jakiś sposób na obejście takich dolnych granic poprzez zaoferowanie słabszych gwarancji? Na przykład, czy może istnieć wersja powyższego lematu dla ℓ

$$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$$ $\ell_1$$\ell_1$metryka, która tylko obiecuje zachować odległości większości punktów, ale może pozostawić niektóre arbitralnie zniekształcone? Który nie daje gwarancji multiplikatywnej dla punktów, które są „zbyt blisko”?

Standardowym odniesieniem dla takiego pozytywnego wyniku jest praca Piotra Indyka o stabilnych rozkładach:

http://people.csail.mit.edu/indyk/st-fin.ps

Pokazuje technikę redukcji wymiarów dla której odległość między dowolną parą punktów nie zwiększa się (o więcej niż współczynnik 1 + ϵ ) ze stałym prawdopodobieństwem, a odległości nie zmniejszają się (o więcej niż współczynnik 1 - ϵ ) z dużym prawdopodobieństwem. Wymiar osadzania będzie wykładniczy w 1 / ϵ .$\ell_1$$1+\epsilon$$1-\epsilon$$1/\epsilon$

Prawdopodobnie są kolejne prace, o których nie wiem.

Zobacz dokument Metryczne osadzanie ze zrelaksowanymi gwarancjami, który ma wyniki na (w warunkach „łagodnie zniekształcającego zniekształcenia”) i ogólne osadzenia ℓ p .$\ell_1$$\ell_p$

Zobacz także praktyczne procedury redukcji wymiarów w pracy .$\ell_1$

Został ostatnio przez Newmana i Rabinovich że dla n punktów w jest zmniejszenie wymiarów na wymiar O ( N / ε ) . Posługując się twierdzeniem Abrahama i in. (Osadzanie metryczne ze swobodnymi gwarancjami, wspomniane powyżej) można uzyskać zmniejszenie wymiaru w wymiarze O ( 1 / ( δ ϵ ) ), który działa dla 1 - $\ell_1$$O(n/\epsilon)$$O(1/(\delta\epsilon))$$1-\delta$ frakcji pary.

Innym rozluźnienie zmniejszenie wymiarów jest wymaganie, że S leży w c -wymiarowej podprzestrzeni R d i Robi k zależą C . Talagrand okazało się , że ze względu na c wymiarową podprzestrzeni V o £ -l , d 1 (okazuje się, że nawet dla L 1 ) istnieje mapę f : £ -l d 1 → £ -l k 1 o K = O ( ε - $\ell_1$$S$$c$$\mathbb{R}^d$$k$$c$$c$$V$$\ell_1^d$$L_1$$f:\ell_1^d \rightarrow \ell_1^k$ tak, że dla wszystkich x , y ∈ V , ( 1 - ϵ ) ‖ f ( x ) - f ( y ) ‖ 1 ≤ ‖ x - y ‖ 1 ≤ ( 1 + ϵ ) ‖ f ( x ) - f ( y ) ‖ $k = O(\epsilon^{-2}c\log c)$$x, y \in V$$(1-\epsilon)\|f(x) - f(y)\|_1 \leq \|x - y\|_1 \leq (1+\epsilon)\|f(x) - f(y)\|_1$. Jego osadzanie jest prostą, losową procedurą, ale przebiega etapami i każdy krok kończy się powodzeniem ze stałym prawdopodobieństwem; po każdym kroku musisz sprawdzić, czy krok rzeczywiście się powiódł i powtórzyć, jeśli nie. Tak więc osadzanie Talagrand nie ma kluczowej cechy JLT: fakt, że można wybrać z rozkładu niezależnego od $f$$S$ .

$f$$S$$k \times d$