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) ):
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 nie są ściśle ortogonalne, gdy ich wpisy są niezależnie wybierane spośród . Dlatego wcześniejsze wersje RP, w których wymuszono ortogonalność kolumn 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 ?.
Odpowiedzi:
Jaka jest definicja projekcji w tym ścisłym (algebraicznym) znaczeniu (słowa)
Masz to do projekcji ortogonalnej lub wektorowej
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:
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:
Wpis w Wikipedii opisuje losową projekcję w ten sposób (to samo wspomniano w notatkach z wykładów na stronach 10 i 11)
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=RTR b=RTx x′=Rb=RTRx RTR
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ładuP=RTR U
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”.
źródło
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 P2=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×k R k≪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×k U
źródło
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×k R R x∈Rd R
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 RTR=I∈Rk×k x R
i staje się macierz projekcji , gdyż jest kwadratowe i .RRT∈Rd×d (RRT)2=RRTRRT=RRT
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 Rk Rd x∈Rd xRRT R RRT
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
źródło
Jeśli użyjesz przeliczalnego losowego odwracania lub permutacji przed szybką transformacją Wamsa Hadamarda, losowa projekcja jest ortogonalna.
źródło