Jaka jest intuicja stojąca za SVD?

Czytałem o rozkładzie wartości pojedynczej (SVD). W prawie wszystkich podręcznikach wspomniano, że rozkłada macierz na trzy macierze o podanej specyfikacji.

Ale jaka jest intuicja dzielenia macierzy w takiej formie? PCA i inne algorytmy redukcji wymiarów są intuicyjne w tym sensie, że algorytm ma ładną właściwość wizualizacji, ale w przypadku SVD tak nie jest.

Zapisz SVD macierzy (rzeczywistej, n × p ) jako X = U D V T, gdzie U to n × p , D to przekątna p × p, a V T to p × p . Jeśli chodzi o kolumny macierzy U i V , możemy napisać X = ∑ p i = 1 d i u i v T $X$$n\times p$

$$X = U D V^T$$ $U$$n\times p$$D$$p\times p$$V^T$$p\times p$$U$$V$$X=\sum_{i=1}^p d_i u_i v_i^T$. To pokazuje zapisany jako suma macierzy p rank-1. Jak wygląda matryca rangi 1? Zobaczmy: ( 1 2 3 ) ( 4 5 6 ) = ( 4 5 6 8 10 12 12 15 18 ) Wiersze są proporcjonalne, a kolumny proporcjonalne.$X$$p$ $$\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} \begin{pmatrix} 4 & 5 & 6 \end{pmatrix} = \begin{pmatrix} 4 & 5 & 6 \\ 8 & 10 & 12 \\ 12 & 15 & 18 \end{pmatrix}$$

Pomyśl teraz o jako zawierającym wartości w skali szarości czarno-białego obrazu, każdy wpis w macierzy reprezentuje jeden piksel. Na przykład następujące zdjęcie pawiana:$X$

Następnie wczytaj ten obraz do R i pobierz część macierzową wynikowej struktury, być może używając biblioteki pixmap.

---

Jeśli potrzebujesz przewodnika krok po kroku, jak odtworzyć wyniki, możesz znaleźć kod tutaj .

---

Oblicz SVD:

baboon.svd  <-  svd(bab) # May take some time

$512 \times 512$$512$$512$$1$$20$

baboon.1  <-  sweep(baboon.svd$u[,1,drop=FALSE],2,baboon.svd$d[1],"*") %*%
                   t(baboon.svd$v[,1,drop=FALSE])

baboon.20 <-  sweep(baboon.svd$u[,1:20,drop=FALSE],2,baboon.svd$d[1:20],"*") %*%
                   t(baboon.svd$v[,1:20,drop=FALSE])

w wyniku czego powstają następujące dwa obrazy:

Po lewej stronie możemy łatwo zobaczyć pionowe / poziome paski na obrazie rangi 1.

$20$

Co jest dość interesujące: widzimy fragmenty oryginalnego obrazu, które trudno jest przedstawić jako superpozycję pionowych / poziomych linii, głównie ukośne włosy na nosie i trochę tekstury oraz oczy!

$A$$m \times n$$m \geq n$$v$$A$

$$\begin{align} \tag{1}v_1 = \,\,& \arg \max_{v \in \mathbb R^n} \quad \| A v \|_2 \\ & \text{subject to } \, \|v\|_2 = 1. \end{align}$$ $v_1$$A$ $$\begin{align} v_2 = \,\,& \arg \max_{v \in \mathbb R^n} \quad \| A v \|_2 \\ & \text{subject to } \,\langle v_1, v \rangle = 0, \\ & \qquad \qquad \, \, \, \, \|v\|_2 = 1. \end{align}$$ $v_1, \ldots, v_n$$\mathbb R^n$$\mathbb R^n$$A$

Niech (więc określa moc wybuchową w kierunku ). Załóżmy, że wektory jednostkowe są zdefiniowane tak, że Równania (2) można wyrazić zwięźle za pomocą notacji macierzowej jako gdzie jest macierzą , której ta kolumna to , jest macierzą , której kolumna to , a$\sigma_i = \|A v_i \|_2$$\sigma_i$$A$$v_i$$u_i$

$$\tag{2} A v_i = \sigma_i u_i \quad \text{for } i = 1, \ldots, n.$$ $$\tag{3} A V = U \Sigma,$$ $V$$n \times n$$i$$v_i$$U$$m \times n$$i$$u_i$$\Sigma$jest macierzą diagonalną, której tym wpisem jest . Macierz jest ortogonalna, więc możemy pomnożyć obie strony (3) przez aby otrzymać Może się wydawać, że wyprowadziliśmy SVD z przy prawie zerowym wysiłku. Żaden z dotychczasowych kroków nie był trudny. Brakuje jednak kluczowego fragmentu obrazu - nie wiemy jeszcze, że jest ortogonalny.$n \times n$$i$$\sigma_i$$V$$V^T$ $$A = U \Sigma V^T.$$ $A$$U$

Oto kluczowy fakt, brakujący element: okazuje się, że jest prostopadła do : Twierdzę, że jeśli to nie była prawda, to nie byłoby optymalne dla problemu (1). Rzeczywiście, jeśli (4) nie byłby spełniony, wówczas można by ulepszyć , zaburzając go nieco w kierunku .$A v_1$$A v_2$

$$\tag{4} \langle A v_1, A v_2 \rangle = 0.$$ $v_1$ $v_1$$v_2$

Załóżmy (dla sprzeczności), że (4) nie jest spełniony. Jeśli jest lekko zaburzone w kierunku ortogonalnym , norma się nie zmienia (lub przynajmniej zmiana normy jest nieistotna). Kiedy chodzę po powierzchni ziemi, moja odległość od jej środka nie zmienia się. Jednakże, gdy jest zaburzone w kierunku , wektor jest zaburzony w nieortogonalnym kierunku , a zatem zmiana normy jest nieistotna . Norma$v_1$$v_2$$v_1$$v_1$$v_1$$v_2$$A v_1$$A v_2$$A v_1$$A v_1$można zwiększyć o nie mniej znaczącą kwotę. Oznacza to, że nie jest optymalny dla problemu (1), co jest sprzecznością. Podoba mi się ten argument, ponieważ: 1) intuicja jest bardzo jasna; 2) intuicję można przekształcić bezpośrednio w rygorystyczny dowód.$v_1$

Podobny argument pokazuje, że jest ortogonalny zarówno dla i i tak dalej. Wektory są parami ortogonalne. Oznacza to, że wektory jednostkowe mogą być wybrane jako pary ortogonalne, co oznacza, że ​​macierz powyżej jest macierzą ortogonalną. To kończy nasze odkrycie SVD.$A v_3$$A v_1$$A v_2$$A v_1, \ldots, A v_n$$u_1, \ldots, u_n$$U$

---

Aby przekonwertować powyższy intuicyjny argument na rygorystyczny dowód, musimy skonfrontować fakt, że jeśli jest zakłócony w kierunku , zaburzony wektor nie jest w rzeczywistości wektorem jednostkowym. (Jego normą jest .) Aby uzyskać dokładny dowód, zdefiniuj Wektor jest naprawdę wektorem jednostkowym. Ale jak można łatwo wykazać, jeśli (4) nie jest spełniony, to dla wystarczająco małych wartości mamy (przy założeniu, że znak$v_1$$v_2$

$$\tilde v_1 = v_1 + \epsilon v_2$$ $\sqrt{1 + \epsilon^2}$ $$\bar v_1(\epsilon) = \sqrt{1 - \epsilon^2} v_1 + \epsilon v_2.$$ $\bar v_1(\epsilon)$$\epsilon$ $$f(\epsilon) = \| A \bar v_1(\epsilon) \|_2^2 > \| A v_1 \|_2^2$$ $\epsilon$jest wybrany poprawnie). Aby to pokazać, po prostu sprawdź, czy . Oznacza to, że nie jest optymalny dla problemu (1), co jest sprzecznością.$f'(0) \neq 0$$v_1$

(Nawiasem mówiąc, polecam czytanie wyjaśnienie Qiaochu juana z SVD tutaj . W szczególności przyjrzeć się „Key lemat # 1”, czyli to, co omówiono powyżej. Jak mówi Qiaochu, klucz lemat nr 1 to „serce techniczny o rozkładzie pojedynczej wartości ”.)

Koleś, poświęć godzinę dnia i obejrzyj ten wykład: https://www.youtube.com/watch?v=EokL7E6o1AE

Ten facet jest bardzo bezpośredni, ważne jest, aby nie pominąć żadnego z nich, ponieważ w końcu wszystko się łączy. Nawet jeśli na początku może się to wydawać trochę powolne, próbuje określić punkt krytyczny, co robi!

Podsumuję to dla ciebie, zamiast po prostu dać ci trzy matryce, które wszyscy robią (ponieważ to mnie pomyliło, gdy przeczytałem inne opisy). Skąd się biorą te matryce i dlaczego tak to konfigurujemy? Wykład to gwoździe! Każdą macierz (kiedykolwiek w historii wieczności) można zbudować z macierzy podstawowej o tych samych wymiarach, a następnie obrócić ją i rozciągnąć (jest to podstawowe twierdzenie algebry liniowej). Każda z tych trzech matryc, którymi ludzie się rzucają, reprezentuje macierz początkową (U), macierz skalowania A (sigma) i macierz obrotu (V).

Macierz skalowania pokazuje, które wektory obrotu dominują, są to tak zwane wartości osobliwe. Rozkład rozwiązuje się dla U, sigma i V.