Izometryczne osadzanie L2 w L1

Wiadomo, że biorąc pod uwagę podzbiór (to znaczy, biorąc pod uwagę punktów w z odległością euklidesową), możliwe jest osadzenie ich izometrycznie w \ ell ^ {n \ wybierz 2 } _1 .$n$$\ell_2^d$$n$${\mathbb R}^d$$\ell^{n\choose 2}_1$

Czy izometria jest obliczalna w (ewentualnie losowym) czasie wielomianowym?

Ponieważ istnieją problemy z precyzją skończoną, dokładne pytanie brzmi:

Biorąc pod uwagę zespół $X$ z $n$ punktów ${\mathbb R}^d$ i $\epsilon >0$ , istnieje odwzorowanie $f: X \to {\mathbb R}^{n\choose 2}$ obliczeniowy (prawdopodobnie, używając przypadkowości), w wielomian czas $n$ oraz logarytmicznych w $1/\epsilon$ , że dla każdego $x,y\in X$ mamy

$|| f(x)-f(y)||_1 \leq ||x-y||_2 \leq (1+ \epsilon) \cdot || f(x)-f(y) ||_1$

(Uwaga: sobie sprawę, że odwzorowanie ze zniekształceniem $(1+\epsilon)$ może być z dużym prawdopodobieństwem w czasie wielomian znaleziono $n$ a $1/\epsilon$ przez wystające w $O(\epsilon^{-2} \cdot \log n)$ losowe linie, ale nie jestem pewien, czy liczbę wymiarów można konstruktywnie zmniejszyć do $n\choose 2$ lub nawet $O(n^2)$ gdy $1/\epsilon$ jest znacznie większy niż $n$ , i nie wiem, czy tam jest jest wielomianem sposób czas obsługi przypadku, w którym $1/\epsilon$ wykładniczo w $n$ ).

Suresh poprosił mnie o połączenie powyższych komentarzy w odpowiedź, więc oto jest. Nie jestem jednak do końca pewien, czy jest to odpowiedź na pierwotne pytanie, ponieważ nie jest oczywiste, jak uczynić go wielomianowym czasem, gdy wymiar wejściowej przestrzeni euklidesowej nie jest stały. Ma przynajmniej tę zaletę, że pozwala uniknąć jakiegokolwiek problemu z dużym jak zadaje oryginalne pytanie, ponieważ nie wymaga żadnego przybliżenia i wygląda na wielomian dla stałej .$1/\epsilon$$d$

Tak czy inaczej: z integralnym geometrii, nie jest standardowym środkiem w zestawach hiperplaszczyzn w -wymiarowej przestrzeni euklidesowej, która jest niezmienna pod euklidesowych kongruencji. Ma właściwość polegającą na tym, że długość dowolnej krzywej ograniczonej długości jest proporcjonalna do miary hiperpłaszczyzn przecinających (z wielokrotnością, co oznacza, że ​​jeśli hiperpłaszczyzna przecina dwa razy, to przyczynia się dwukrotnie do całkowitej miary hiperpłaszczyzn przecinających ). W szczególności, jeśli jest segmentem linii, komplikacja wielokrotności nie powstaje i możemy znormalizować miarę na hiperpłaszczyznach przecinających aby była dokładnie długością$d$$C$$C$$C$$C$$C$$C$$C$. (Hiperplany zawierające mają miarę zero, więc nie martw się o nieskończoną wielokrotność.)$C$

Teraz, mając zestaw n punktów w przestrzeni d-wymiarowej, współrzędną dla każdej z części punktów w dwa podzbiory indukowane przez hiperpłaszczyznę, która nie przechodzi przez żaden z punktów. Podaj punkty po jednej stronie wartości współrzędnej podziału zero, a punkty po drugiej stronie wartości współrzędnej podziału równe miary zbioru hiperpłaszczyzn indukujących ten podział.$\ell_1$

Jeśli i są dowolnymi dwoma z punktów, niech będzie zbiorem hiperpłaszczyzn przecinających odcinek linii , i niech będzie podzbiorami utworzonymi przez każdą możliwą partycję hiperpłaszczyzny, która ma po jednej stronie i po drugiej. Zatem jest rozłącznym związkiem , a różnice współrzędnych między i są tylko miarami podzbiorów . Dlatego odległość między koordynacjami i$p$$q$$n$$K$$pq$$K_i$$K$$p$$q$$K$$K_i$$p$$q$$K_i$$\ell_1$$p$$q$ (suma miar ) jest miarą , która jest tylko oryginalną odległością między i .$K_i$$K$$\ell_2$$p$$q$

W przypadku geometrii obliczeniowej pomocny może być alternatywny opis tej samej konstrukcji: użyj dualności rzutowej, aby przekształcić punktów wejściowych w hiperpłaszczyzn i rozdzielić hiperpłaszczyzny na punkty. Całkowa miara geometrii na zestawach hiperpłaszczyzn jest następnie przekształcana w bardziej standardową miarę na zestawach punktów, odległość między i ulega dualizacji do miary podwójnego klina między dwoma hiperpłaszczyznami, a układ hiperpłaszczyzny dzieli ten podwójny klin na mniejsze komórki . Wartość współrzędnych dla punktu jest albo miarą jednej z komórek w układzie (jeśli podwójna hiperpłaszczyzna znajduje się poniżej komórki tej współrzędnej), albo zero (jeśli podwójna hiperpłaszczyzna znajduje się powyżej komórki). Dlatego też$n$$n$$p$$q$$\ell_1$ odległość między i jest po prostu sumą miar komórek w podwójnym klinie, która jest taka sama jak miara całego podwójnego klina. Ten podwójny punkt widzenia ułatwia również obliczenie znalezionego w ten sposób wymiaru osadzania: jest to tylko liczba komórek w układzie hiperpłaszczyzny, która wynosi , a dokładniej co najwyżej .$p$$q$$O(n^d)$$\sum_{i=0}^d{n\choose i}$

Jak dotąd daje to całkowicie deterministyczne i dokładne osadzenie w . Ale chcieliśmy mniejszego wymiaru, . Tutaj pojawia się komentarz Lucy na temat twierdzenia Carathéodory'ego . Zestaw metryk reprezentowanych przez tworzy stożek wielościenny w przestrzeni wymiarowej wszystkich funkcji od nieuporządkowanych par punktów do liczb rzeczywistych, a powyższy argument geometryczny mówi, że metryka euklidesowa należy do tego stożka. Punkty skrajnych promieni stożka są jednowymiarowe$\ell_1^{O(n^d)}$$\ell_1^{n\choose 2}$$\ell_1$$n\choose 2$$\ell_1$pseudometria (w której punkty są podzielone na dwa zestawy, wszystkie odległości w jednym zestawie są zerowe, a wszystkie odległości w poprzek podziału są równe), a Carathéodory mówi, że dowolny punkt w stożku (w tym ten, na którym nam zależy) może być reprezentowane jako wypukła kombinacja punktów na ekstremalnych promieniach, których liczba jest co najwyżej wymiarem otaczającej przestrzeni, . Ale wypukła kombinacja co najwyżej jednowymiarowe metryki to metryka .$n\choose 2$$n\choose 2$$\ell_1$$\ell_1^{n\choose 2}$

Wreszcie, w jaki sposób możemy faktycznie obliczyć osadzanie wymiarowe? W tym momencie nie mamy tylko punktu w wymiarowy wypukły stożek metryki (metryka odległości, od której zaczęliśmy), ale mamy również zestaw skrajnych punktów (odpowiadające podziałom wejścia na dwa podzbiory indukowane przez hiperpłaszczyzny) tak, że nasza metryka jest wypukłą kombinacją tych skrajnych punktów - dla małego jest to duża poprawa w stosunku do ekstremalnych promieni które stożek ma ogólny. Teraz wszystko, co musimy zrobić, to zastosować chciwy algorytm, który pozbywa się ekstremalnych punktów z naszego zestawu, jeden po drugim, aż tylko$n\choose 2$$n\choose 2$$\ell_1$$O(n^d)$$d$$2^n-2$$n\choose 2$z nich zostało. Na każdym kroku musimy zachować jako niezmienność to, że nasza metryka nadal znajduje się w wypukłym kadłubie pozostałych skrajnych punktów, co jest tylko liniowym problemem wykonalności programowania, a jeśli to zrobimy, Carathéodory zapewni, że zawsze pozostanie zestaw skrajne punkty, których wypukły kadłub zawiera dane wejściowe.$n\choose 2$