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

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?

Odpowiedzi:

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$