Czy „losowa projekcja” ściśle nie jest projekcją?

Obecne implementacje algorytmu losowej projekcji zmniejszają wymiarowość próbek danych poprzez mapowanie ich z do przy użyciu macierzy projekcji d \ razy k R, której wpisy znajdują się w odpowiednim rozkładzie (na przykład z \ matematyka N (0,1) ):$\mathbb R^d$$\mathbb R^k$$d\times k$$R$$\mathcal N(0,1)$

$x^\prime = \frac{1}{\sqrt k}xR$

Dogodnie istnieją teoretyczne dowody wskazujące, że to odwzorowanie w przybliżeniu zachowuje odległości parami.

Jednak ostatnio znalazłem te notatki, w których autor twierdzi, że to odwzorowanie za pomocą macierzy losowej nie jest rzutowaniem w ścisłym liniowym algebraicznym znaczeniu tego słowa (strona 6). Z podanych tam wyjaśnień wynika to z faktu, że kolumny $R$ nie są ściśle ortogonalne, gdy ich wpisy są niezależnie wybierane spośród $\mathcal N(0,1)$ . Dlatego wcześniejsze wersje RP, w których wymuszono ortogonalność kolumn $R$ można uznać za rzut.

Czy możesz podać bardziej szczegółowe wyjaśnienie (1), jaka jest definicja projekcji w tym ścisłym znaczeniu i (2) dlaczego RP nie jest projekcją w ramach tej definicji ?.

1. Jaka jest definicja projekcji w tym ścisłym (algebraicznym) znaczeniu (słowa)

   https://en.wikipedia.org/wiki/Projection_(linear_algebra)

   W Algebra liniowej i analizy funkcjonalnej, występ jest liniową transformację z przestrzeni wektorowej do siebie tak, że . Oznacza to, że ilekroć stosuje się dwukrotnie do dowolnej wartości, daje taki sam wynik, jak gdyby zastosowano je raz (idempotent).$P$$P^2 = P$$P$

   Masz to do projekcji ortogonalnej lub wektorowej

   https://en.wikipedia.org/wiki/Projection_(linear_algebra)

   Rzut ortogonalny to rzut, dla którego zakres U i przestrzeń zerowa V są podprzestrzeniami ortogonalnymi.

2. Dlaczego RP nie jest projekcją w ramach tej definicji?

   Michael Mahoney pisze w notatkach z wykładu, że to zależy od tego, jak zbudowana jest RP , niezależnie od tego, czy RP jest rzutem w tradycyjnym algebraicznym sensie liniowym. Robi to w trzecim i czwartym punkcie:

   Po trzecie, gdyby losowe wektory były dokładnie ortogonalne (tak jak były w oryginalnych konstrukcjach JL), to mielibyśmy, że rzut JL był rzutem ortogonalnym

   ...

   ale chociaż jest to fałsz dla Gaussów, zmiennych losowych i większości innych konstrukcji, można udowodnić, że wektory powstałe w przybliżeniu mają długość jednostkową i w przybliżeniu prostopadłą$\lbrace \pm \rbrace$

   ...

   to jest „wystarczająco dobre”.

   Można więc zasadniczo wykonać losową projekcję o innej konstrukcji, która jest ograniczona do macierzy ortogonalnych (chociaż nie jest to potrzebne). Zobacz na przykład oryginalne dzieło:

   Johnson, William B. i Joram Lindenstrauss. „Rozszerzenia mapowań Lipschitza w przestrzeń Hilberta”. Współczesna matematyka 26.189-206 (1984): 1.

   ... jeśli ktoś wybiera losowo postój rzucie prostokątnym na$k$$l_2^n$

   ...

   Aby to dokładniej pozwolimy się występ na pierwszym współrzędnych i pozwolić znormalizować Haar środka w , prostopadłym grupy w . Następnie zmienna losowa zdefiniowana przez określa pojęcie „ rzutu losowego r ”.$Q$$k$$l_2^n$$\sigma$$O(n)$$l_2^n$

   $$f: (O(n), \sigma) \to L(l_2^n)$$ $$f(u) = U^\star Q U$$ $k$

   Wpis w Wikipedii opisuje losową projekcję w ten sposób (to samo wspomniano w notatkach z wykładów na stronach 10 i 11)

   https://en.wikipedia.org/wiki/Random_projection#Gaussian_random_projection

   Pierwszy rząd to losowy wektor jednostkowy wybrany jednolicie spośród . Drugi rząd to losowy wektor jednostek z przestrzeni ortogonalnej do pierwszego rzędu, trzeci rząd to losowy wektor jednostek z przestrzeni ortogonalnej do pierwszych dwóch rzędów i tak dalej.$S^{d − 1}$

   Ale na ogół nie uzyskuje się tej ortogonalności, gdy weźmie się wszystkie wpisy macierzy w macierzowych zmiennych losowych i niezależnych o rozkładzie normalnym (jak Whuber wspomniał w swoim komentarzu z bardzo prostą konsekwencją) „jeśli kolumny byłyby zawsze ortogonalne, ich wpisy mogłyby nie być niezależnym ”).

   Macierz i iloczyn w przypadku kolumn ortonormalnych można postrzegać jako rzut, ponieważ dotyczy macierzy rzutowania . To trochę tak samo, jak widzenie zwykłej regresji metodą najmniejszych kwadratów jako projekcji. Iloczyn nie jest rzutem, ale daje współrzędną w innym wektorze bazowym. „Prawdziwa” projekcja to , a macierz projekcji to .$R$$P = R^TR$$b = R^T x$$x' = Rb = R^TRx$$R^TR$

   Macierz projekcji musi być operatorem tożsamości w podprzestrzeni która jest zakresem projekcji (patrz właściwości wspomniane na stronie wikipedii). Lub inaczej powiedział, że musi mieć wartości własne 1 i 0, tak, że podprzestrzeń, dla której jest to matryca tożsamości, jest rozpiętością wektorów własnych powiązanych z wartościami własnymi 1. Przy losowych wpisach macierzy nie uzyskasz tej właściwości. To drugi punkt notatek z wykładu$P=R^TR$$U$

   ... na wiele sposobów „wygląda jak” macierz ortogonalna ... jest równomiernie rozmieszczoną podprzestrzenią ... ale wartości własne nie są w .$range(P^T P)$$\lbrace 0, 1 \rbrace$

   ^{należy zauważyć, że w tym cytacie macierz odnosi się do macierzy w pytaniu, a nie do macierzy projekcji implikowanej przez macierz$P$$R$$P = R^TR$$R$}

   Tak więc losowe odwzorowanie przez różne konstrukcje, takie jak użycie losowych wpisów w macierzy, nie jest dokładnie równe rzutowi ortogonalnemu. Ale jest obliczeniowo prostszy i według Michaela Mahoneya jest „wystarczająco dobry”.

Zgadza się: „losowa projekcja” ściśle nie jest projekcją.

Występ A jest wyraźnie zdefiniowane matematycznego obiekt: https://en.wikipedia.org/wiki/Projection_(linear_algebra) - jest liniowy operatora idempotentent, czyli liniowy operatora takie, że . Dwukrotne zastosowanie projekcji jest tym samym, co zastosowanie jej tylko raz, ponieważ po rzutowaniu punktu na podprzestrzeń, powinno pozostać tam, jeśli zostanie ponownie wyświetlone. W tej definicji nie ma nic o ortogonalności; w rzeczywistości projekcja może być ukośna (patrz Wikipedia).$P$$P^2 = P$

Zauważ, że tylko macierze kwadratowe mogą reprezentować „rzuty” w tym sensie. „Projekcja losowa” wykorzystuje losową macierz z , więc nie może to być projekcja w rozumieniu powyższej definicji.$d\times k$$R$$k\ll d$

Nawet jeśli utworzysz kolumny ortonormalne (np. Stosując proces Gram-Schmidta), ten argument będzie nadal obowiązywał. Ktoś niedawno zadał to pytanie dotyczące PCA: co dokładnie powinno być nazwane „matrycą projekcyjną” w kontekście PCA? - macierz ortonormalnych wektorów własnych nie jest też ściśle odwzorowaniem.$R$$d\times k$$U$

Myślę, że kluczem tutaj jest rozważenie przestrzeni kolumn macierzy RP jako podprzestrzeni, na którą wykonujemy projekcję. Zasadniczo, niezależnie od tego, czy kolumny są ortogonalne, można rzutować próbkę na przestrzeń kolumny za pomocą następującego równania [1]:$d\times k$$R$$R$$x\in \mathbb R^d$$R$

$p = xR(R^TR)^{-1}R^T$ , gdzie .$p\in\mathbb R^d$

Jeśli jak w starszych wersjach lub RP, kolumny macierzy są ograniczone do ortonormalnych, wówczas , a zatem rzut na przestrzeń kolumny staje się:$R$$R^TR = I\in \mathbb R^{k\times k}$$x$$R$

$p = xRR^T$ , z ,$p\in\mathbb R^d$

i staje się macierz projekcji , gdyż jest kwadratowe i .$RR^T\in\mathbb R^{d\times d}$$(RR^T)^2=RR^TRR^T=RR^T$

Być może twierdzenie, że starsza wersja Projekcji Losowej (gdzie kolumny były ortonormalne) jest w rzeczywistości projekcją odnoszącą się do faktu, że w takim przypadku osadzenie do i tylna rekonstrukcja z powrotem do próbki podanej przez jest rzeczywiście rzutem na przestrzeń kolumny , a jest macierzą rzutowania .$R$$\mathbb R^k$$\mathbb R^d$$x\in\mathbb R^d$$xRR^T$$R$$RR^T$

Byłbym wdzięczny, gdyby mógł Pan potwierdzić / poprawić moje rozumowanie tutaj.

Odniesienie:

[1] http://www.dankalman.net/AUhome/classes/classesS17/linalg/projections.pdf

Jeśli użyjesz przeliczalnego losowego odwracania lub permutacji przed szybką transformacją Wamsa Hadamarda, losowa projekcja jest ortogonalna.