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

Biorąc pod uwagę aproksymację PCA (lub SVD) macierzy z macierzą , wiemy, że jest najlepszym przybliżeniem niskiej rangi . $X$ $\hat X$ $\hat X$ $X$

Czy jest to zgodne z indukowaną normą $\parallel \cdot \parallel_2$ (tj. Największą normą wartości własnej), czy zgodnie z normą Frobenius ? $\parallel \cdot \parallel_F$

pca svd matrix-decomposition

— Donbeo
źródło

Odpowiedź na jedno słowo: oba.

$X$ $2$

‖ X ‖_{2} = s u p \frac{‖ X v ‖_{2}}{‖ v ‖_{2}} = m a x (s_{i})

$\|X\|_2 = \mathrm{sup}\frac{\|Xv\|_2}{\|v\|_2} = \mathrm{max}(s_i)$

‖ X ‖_{F} = \sqrt{\sum_{i j} X_{i j}^{2}} = t r (X^{⊤} X) = \sqrt{\sum s_{i}^{2}},

$\|X\|_F = \sqrt {\sum_{ij} X_{ij}^2} = \mathrm{tr}(X^\top X) = \sqrt{\sum s_i^2},$

s_{i}

$s_i$

X

$X$

S

$S$

X = U S V^{⊤}

$X = USV^\top$

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 . $US$ $V$ $X$ $k$ $k$ $X_k = U_k S_k V_k^\top$

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_k$ $\|X-A\|$ $A$ $k$ $2$

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.

Eckart and Young, 1936, Przybliżenie jednej macierzy przez inną niższą rangę
Mirsky, 1958, Funkcje miernika symetrycznego i jednolicie niezmienne normy
Stewart, 1993, O wczesnej historii osobliwego rozkładu wartości

Dowód dla operatora normalny $2$

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. $X$ $n$ $A$ $k$ $n-k$ $k+1$ $X$ $k+1$ $w$

‖ X - A ‖_{2}^{2} \geq ‖ (X - A) w ‖_{2}^{2} = ‖ X w ‖_{2}^{2} = \sum_{i = 1}^{k + 1} s_{i}^{2} (v_{i}^{⊤} w)^{2} \geq s_{k + 1}^{2} = ‖ X - X_{k} ‖_{2}^{2},

$\|X-A\|^2_2 \ge \|(X-A)w\|^2_2 = \|Xw\|^2_2 = \sum_{i=1}^{k+1}s_i^2(v_i^\top w)^2 \ge s_{k+1}^2 = \|X-X_k\|_2^2,$

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. $A$ $k$ $\|X-A\|^2_F$ $A=BW^\top$ $W$ $k$ $\|X-BW^\top\|^2$ $W$ $B=XW$

‖ X - X W W^{⊤} ‖^{2} = ‖ X ‖^{2} - ‖ X W W^{⊤} ‖^{2} = c o n s t - t r (W W^{⊤} X^{⊤} X W W^{⊤}) = c o n s t - c o n s t \cdot t r (W^{⊤} Σ W),

$\|X-XWW^\top\|^2=\|X\|^2-\|XWW^\top\|^2=\mathrm{const}-\mathrm{tr}(WW^\top X^\top XWW^\top)\\=\mathrm{const}-\mathrm{const}\cdot\mathrm{tr}(W^\top\Sigma W),$

Σ

$\Sigma$

X

$X$

Σ = X^{⊤} X / (n - 1)

$\Sigma=X^\top X/(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

$W$

k

$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. $k$ $X=USV^\top$ $\Sigma=VS^2V^\top/(n-1)=V\Lambda V^\top$ $R=V^\top W$

t r ({W.}^{⊤} Σ W.) = t r (R^{⊤} Λ R) = \sum_{ja} λ_{ja} \sum_{jot} R_{ja jot}^{2)} \leq \sum_{ja = 1}^{k} λ_{k},

$\mathrm{tr}(W^\top\Sigma W)=\mathrm{tr}(R^\top\Lambda R)=\sum_i \lambda_i \sum_j R_{ij}^2 \le \sum_{i=1}^k \lambda_k,$

W = V_{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 - ZA ‖_{fa} = ‖ U S. {V.}^{⊤} - ZA ‖ = ‖ S. - U^{⊤} ZA V. ‖ = ‖ S. - b ‖,

$\|X-A\|_F=\|USV^\top - A\| = \|S - U^\top A V\| = \|S-B\|,$

B = U^{⊤} A V

$B=U^\top A V$

‖ X - ZA ‖_{fa} = \sum_{ja jot} ({S.}_{ja jot} - b_{ja jot})^{2)} = \sum_{ja} (s_{ja} - b_{ja ja})^{2)} + \sum_{ja \neq jot} b_{ja jot}^{2)} .

$\|X-A\|_F = \sum_{ij}(S_{ij}-B_{ij})^2 = \sum_i (s_i-B_{ii})^2 + \sum_{i\ne j}B_{ij}^2.$

B

$B$

k

$k$

k

$k$

s_{i}

$s_i$

B_{o p t i m a l} = S_{k}

$B_\mathrm{optimal}=S_k$

A_{o p t i m a l} = U_{k} S_{k} V_{k}^{⊤}

$A_\mathrm{optimal} = U_k S_k V_k^\top$

— ameba mówi Przywróć Monikę
źródło

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ł

Zauważ też, że SVD był znany Beltrami (przynajmniej w dość ogólnym, choć szczególnym przypadku) i Jordanii już w 1874 r.

— kardynał

B

$B$

S

$S$

k

$k$

\sum_{i} (s_{i} - B_{i i})^{2}

$\sum_{i}(s_i-B_{ii})^2$

\sum_{i \neq j} B_{i j}^{2}

$\sum_{i\ne j}B_{ij}^2$

— ameba mówi Przywróć Monikę

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ł

@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ę

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

Odpowiedź na jedno słowo: oba.

Dowód dla operatora normalny222

Dowód normy Frobenius

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

Dowód dla operatora normalny $2$