Jaką normę błędu rekonstrukcji minimalizuje macierz aproksymacji niskiego rzędu uzyskana za pomocą PCA?

Odpowiedzi:

30

Odpowiedź na jedno słowo: oba.


X2XF=

X2=supXv2v2=max(si)
siXSX=USV
XF=ijXij2=tr(XX)=si2,
siXSX=USV

PCA otrzymuje ten sam rozkład wartości w liczbie pojedynczej, gdy dane są wyśrodkowane. są głównymi składnikami, są głównymi osiami, tj. Wektorami własnymi macierzy kowariancji, a rekonstrukcję z tylko głównymi składnikami odpowiadającymi największym pojedynczym wartościom daje .V X k k X k = U k S k V kUSVXkkXk=UkSkVk

Twierdzenie Eckarta-Younga mówi, że jest macierzą minimalizującą normę błędu rekonstrukcjispośród wszystkich macierzy rangi . Dotyczy to zarówno normy Frobeniusa, jak i operatora -norm. Jak zauważył @cardinal w komentarzach, po raz pierwszy udowodnił to Schmidt (sława Gram-Schmidta) w 1907 r. W sprawie Frobenius. Później został ponownie odkryty przez Eckarta i Younga w 1936 r. I obecnie jest kojarzony głównie z ich nazwami. Mirsky uogólnił twierdzenie z 1958 r. Na wszystkie normy niezmienne przy przekształceniach jednostkowych, w tym na operatora 2-normę.X - A A k 2XkXAAk2

Twierdzenie to jest czasem nazywane twierdzeniem Eckarta-Younga-Mirsky'ego. Stewart (1993) nazywa to twierdzeniem przybliżenia Schmidta. Widziałem nawet, że nazywa się to twierdzeniem Schmidta-Eckarta-Younga-Mirsky'ego.


Dowód dla operatora normalny2

Niech będzie pełnej rangi . Ponieważ ma rangę , jego pusta przestrzeń ma wymiary . Przestrzeń łączona przez prawych wektorów pojedynczych odpowiadających największym wartościom pojedynczym ma wymiary . Te dwie przestrzenie muszą się przecinać. Niech będzie wektorem jednostkowym od przecięcia. Następnie otrzymujemy: QED.n A k n - k k + 1 X k + 1 w X - A 2 2( X - A ) w 2 2 = X w 2 2 = k + 1 i = 1 s 2 i ( v i w ) 2s 2XnAknkk+1Xk+1w

XA22(XA)w22=Xw22=i=1k+1si2(viw)2sk+12=XXk22,

Dowód normy Frobenius

Chcemy znaleźć macierz rangi która minimalizuje . Możemy faktoryzować , gdzie ma kolumn ortonormalnych. Minimalizowanie dla ustalonego jest problemem regresji z rozwiązaniem . Podłączając go, widzimy, że musimy teraz zminimalizować gdzie jest macierzą kowariancji , tj.AkXAF2A=BWWkXBW2WB=XW

XXWW2=X2XWW2=consttr(WWXXWW)=constconsttr(WΣW),
ΣXΣ=XX/(n-1). Oznacza to, że błąd rekonstrukcji jest zminimalizowane poprzez jako kolumny niektórych wektorów ortonormalnych zwiększając całkowitą wariancję projekcji.W.k

Jest dobrze wiadomo, że są to pierwsze wektory własne macierzy kowariancji. Rzeczywiście, jeśli , to . Pisząc który ma również kolumny ortonormalne, otrzymujemy z maksimum osiągniętym, gdy . Twierdzenie to następuje natychmiast.kX=US.V.Σ=V.S.2)V./(n-1)=V.ΛV.R=V.W.

tr(W.ΣW.)=tr(RΛR)=jaλjajotRjajot2)ja=1kλk,
W.=V.k

Zobacz następujące trzy powiązane wątki:


Wcześniejsza próba dowodu zgodności z normą Frobenius

Ten dowód znalazłem gdzieś w Internecie, ale jest błędny (zawiera lukę), jak wyjaśniono w @cardinal w komentarzach.

Norma Frobeniusa jest niezmienna w jednostkowych przekształceniach, ponieważ nie zmieniają one wartości pojedynczych. Otrzymujemy więc: gdzie . Kontynuacja:Przy czym minimalizuje się przy wszystkich elementów niediagonalnych są równe zero, a wszystkie ukośne warunki niwelować największych wartości singularnych [szczelinę na: nie jest to oczywiste] tj a więc .

X-ZAfa=US.V.-ZA=S.-UZAV.=S.-b,
b=UZAV.
X-ZAfa=jajot(S.jajot-bjajot)2)=ja(sja-bjaja)2)+jajotbjajot2).
bkksja boptjamzal=S.kZAoptjamzal=UkS.kV.k
ameba mówi Przywróć Monikę
źródło
2
Dowód w przypadku normy Frobeniiusa nie jest poprawny (lub przynajmniej kompletny), ponieważ argument tutaj nie wyklucza możliwości, że matryca o tej samej wartości mogłaby anulować niektóre inne terminy przekątne, mając jednocześnie „małe” przekątne. Aby lepiej widzieć różnicę, zauważ, że utrzymywanie stałych przekątnych i „zerowanie” przekątnych może często zwiększać rangę omawianej macierzy!
kardynał
1
Zauważ też, że SVD był znany Beltrami (przynajmniej w dość ogólnym, choć szczególnym przypadku) i Jordanii już w 1874 r.
kardynał
bS.kja(sja-bjaja)2)jajotbjajot2)
ameba mówi Przywróć Monikę
3
I robić jak GW Stewarta (1993) Na początku historii Rozkład według wartości osobliwych, SIAM Review , vol. 35, nr 4, 551–566, a biorąc pod uwagę wcześniejsze zainteresowanie sprawami historycznymi, myślę, że Ty również. Niestety uważam, że Stewart nieumyślnie zbyt lekceważy elegancję dowodu Schmidta z 1907 roku. Ukryta w nim jest interpretacja regresji, którą Stewart przeoczy i która jest naprawdę całkiem ładna. Jest inny dowód, który podąża za początkowym podejściem do diagonalizacji, ale wymaga dodatkowej pracy, aby wypełnić lukę. (cd.)
kardynał
2
@cardinal: Tak, masz rację, teraz też widzę lukę. Bardzo dziękuję za artykuł Stewarta, który był bardzo interesującą lekturą. Widzę, że Stewart przedstawia dowody Schmidta i Weyla, ale oba wyglądają na bardziej skomplikowane niż to, co chciałbym tutaj skopiować (i jak dotąd nie miałem czasu na ich dokładne przestudiowanie). Jestem zaskoczony: spodziewałem się, że będzie to bardzo prosty wynik, ale wydaje się, że jest mniej trywialny, niż myślałem. W szczególności nie spodziewałbym się, że sprawa Frobeniusa jest o wiele bardziej skomplikowana niż normalna operacyjna. Będę teraz edytować post. Szczęśliwego Nowego Roku!
ameba mówi Przywróć Monikę