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

10

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) ):RdRkd×kRN(0,1)

x=1kxR

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 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 ?.

Daniel López
źródło
1
Możesz znaleźć odpowiedzi na (1), przeszukując naszą stronę . Twierdzenie (2) jest natychmiastowe, ponieważ gdyby kolumny były zawsze ortogonalne, ich wpisy nie mogłyby być niezależne.
whuber

Odpowiedzi:

4
  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).PP2=PP

    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łą{±}

    ...

    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 nakl2n

    ...

    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 ”.Qkl2nσO(n)l2n

    f:(O(n),σ)L(l2n)
    f(u)=UQU
    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.Sd1

    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 .RP=RTRb=RTxx=Rb=RTRxRTR

    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=RTRU

    ... na wiele sposobów „wygląda jak” macierz ortogonalna ... jest równomiernie rozmieszczoną podprzestrzenią ... ale wartości własne nie są w .range(PTP){0,1}

    należy zauważyć, że w tym cytacie macierz odnosi się do macierzy w pytaniu, a nie do macierzy projekcji implikowanej przez macierzPRP=RTRR

    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”.

Sextus Empiricus
źródło
1
Dzięki za odpowiedź, myślę, że idzie w tym samym kierunku co ten, który podałem powyżej. Właśnie w celu wyjaśnienia Myślę, że należy wskazać, że . Zatem, jak wyjaśnisz, jeśli wpisy są oznaczone jako nie możemy zapewnić, że lub że ma wartości własne w . I odwrotnie, jeśli kolumny są ortonormalne, oba warunki są spełnione. Ale kluczem jest wskazanie, że rzut jest , a nie tylko ! P=RRTRRd×kN(0,1)P2=PP{0,1}RRRTR
Daniel López,
1
@ DanielLópez Zaktualizowałem go.
Sextus Empiricus,
6

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).PP2=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×kRkd

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.Rd×kU

ameba
źródło
3
W ostatnim akapicie mówisz, że jeśli kolumny są ortonormalne, to projekcja nadal nie jest projekcją w sensie projekcji w algebrze liniowej. Jest tak jednak tylko dlatego, że macierz nie jest macierzą kwadratową. Jest to bardziej spowodowane notacją niż zasadą. Jeśli rozszerzysz macierz o zero, to macierz jest rzutem liniowym.
Sextus Empiricus,
1
@MartijnWeterings Nie, nie sądzę. Weź przestrzeń 2D i U, które wynosi 1x2 i wygląda następująco: [sqrt (2) / 2, sqrt (2) / 2] (odpowiadający rzutowi na przekątnej). Teraz przedłuż go zerami. Nie będzie równy sobie do kwadratu.
ameba
1
Należy go rozszerzyć w inny sposób, można to zrobić
kjetil b halvorsen,
2
@amoeba, że zgadzają się, że rozciąganie koncepcji / definicji, ale powiedzieć, że jest ona bardziej złożony niż , które to określenie obejmuje odwrotną nie jest równa . Kombinacja liniowa gdy jest wykonana z wektorów ortogonalnych, przypomina rzut ortogonalny na mniejszą podprzestrzeń i można powtórzyć ten rzut, uzyskując to samo. Tyle tylko, że wraz z rzutowaniem wybierany jest inny zestaw wektorów bazowych (przynajmniej tak można to zobaczyć), a reprezentacja macierzy nie działa jak , ale geometrycznie wygląda jak rzut. R(RTR)1RTIUP2=P
Sextus Empiricus,
2
Zgadza się, @MartijnWeterings, ale dlaczego jakikolwiek z nieortogonalnymi kolumnami nie miałby wyglądać jak skośna projekcja ? R
ameba
1

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×kRRxRdR

p=xR(RTR)1RT , gdzie .pRd

Jeśli jak w starszych wersjach lub RP, kolumny macierzy są ograniczone do ortonormalnych, wówczas , a zatem rzut na przestrzeń kolumny staje się:RRTR=IRk×kxR

p=xRRT , z ,pRd

i staje się macierz projekcji , gdyż jest kwadratowe i .RRTRd×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 .RRkRdxRdxRRTRRRT

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

Daniel López
źródło
1
To prawda, ale dla dowolnego R macierz , której używasz w pierwszej formule, jest również rzutem. Nie sądzę więc, że ortogonalność kolumn R ma znaczenie dla argumentu podanego w ostatnim akapicie. R(RTR)1RT
ameba
1
To prawda, ale chodziło mi o to, że może chcesz, aby była matrycą projekcji, ponieważ pasuje ona do naturalnego osadzenia i rekonstruuje logikę redukcji wymiarów. Również w ten sposób kolumny tworzą ortonormalną podstawę podprzestrzeni (przestrzeń kolumny R). Skontaktuję się z autorem notatek, aby sprawdzić, czy mogą rzucić na to trochę światła. Dzięki za odpowiedź! RRTR
Daniel López,
2
@amoeba macierz jest rzeczywiście także rzutowaniem, ale rzutowanie losowe nie wykorzystuje części , ale zamiast tego . Kiedy trzeba ortonormalnych kolumny czym ten pseudo odwrotnego części odpowiada macierzy . Można to zobaczyć podobnie jak w przypadku OLS, obliczając , jako projekcję, ale współczynniki nie są projekcją. OLS jest wyłącznie projekcją, gdy obliczasz . Mimo to można uznać za projekcję na innej podstawie. To bardziej przypomina semantyczną rzecz niż matematykę. ( R t R ) - 1 R , T R t R , T β = ( R t R ) - 1 R T T β R = R ( R t R ) - 1 R T T βR(RTR)1RT(RTR)1RTRTRTβ=(RTR)1RTyβy^=R(RTR)1RTyβ
Sextus Empiricus
-1

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

Sean O'Connor
źródło