Dlaczego nie mogę uzyskać prawidłowego SVD X za pomocą rozkładu wartości własnych XX 'i X'X?

Próbuję wykonać SVD ręcznie:

m<-matrix(c(1,0,1,2,1,1,1,0,0),byrow=TRUE,nrow=3)

U=eigen(m%*%t(m))$vector
V=eigen(t(m)%*%m)$vector
D=sqrt(diag(eigen(m%*%t(m))$values))

U1=svd(m)$u
V1=svd(m)$v
D1=diag(svd(m)$d)

U1%*%D1%*%t(V1)
U%*%D%*%t(V)

Ale ostatnia linia nie mwraca. Dlaczego? Wydaje się, że ma to coś wspólnego z oznakami tych wektorów własnych ... Czy też źle zrozumiałem procedurę?

r svd eigenvalues

— failedstatistician
źródło

Zobacz stats.stackexchange.com/search?q=svd+sign .

— whuber

Wielokrotnie mówiono mi, że znak nie ma znaczenia w SVD ... tak to

— failedstatistician

@Amoeba Dziękujemy za wyjaśnienie tego. Koncentrowałem się raczej na pytaniu angielskim niż na kodzie. Failedstatistician: zobacz, co D=diag(c(-1,1,1)*sqrt(eigen(m%*%t(m))$values))robi i pamiętaj, że pierwiastek kwadratowy (jak również każdy znormalizowany wektor własny) jest definiowany tylko do znaku. Aby uzyskać więcej wglądu, zmiany mdo m <- matrix(-2,1,1)i zawierają ,1,1)na końcu każdego z wywołań diag. Jest to przykład który stwarza ten sam problem - ale jest to tak proste, że charakter problemu stanie się całkowicie oczywisty.

1 \times 1

$1\times 1$

— whuber

Rozumiem. Dziękuję Ci! Czy masz ogólną zasadę określania wektora c (-1, 1, 1)? Lub w jaki sposób powiązać oznaki dwóch dekompozycji?

— failedstatistician

Zauważ, że sztuczka @ Whubera z c(-1,1,1)działa, ale Dzdefiniowana w ten sposób nie daje ci pojedynczych wartości. Wszystkie wartości osobliwe muszą być z definicji dodatnie. Pytanie, jak połączyć znaki Ui, Vjest dobre i nie mam odpowiedzi. Dlaczego nie zrobisz SVD? :-)

— ameba

Odpowiedzi:

Analiza problemu

SVD matrycy nigdy nie jest unikalne. Niech macierz ma wymiary i niech jej SVD będzie $A$ $n\times k$

A = U D V^{'}

$A = U D V^\prime$

dla macierzy z kolumnami ortonormalnymi, diagonalnej macierzy z nieujemnymi wpisami oraz macierzy z kolumnami ortonormalnymi. $n\times p$ $U$ $p\times p$ $D$ $k\times p$ $V$

Teraz wybrać, dowolnie każdy diagonalny macierzy o s po przekątnej, tak, jest tożsamość . Następnie $p\times p$ $S$ $\pm 1$ $S^2 = I$ $p\times p$ $I_p$

A = U D V^{'} = U I D I V^{'} = U (S^{2}) D (S^{2}) V^{'} = (U S) (S D S) (V S)^{'}

$A = U D V^\prime = U I D I V^\prime = U (S^2) D (S^2) V^\prime = (US) (SDS) (VS)^\prime$

jest SVD ponieważ pokazuje ma ortonormalnych kolumny i podobne obliczenia pokazują, że ma kolumny ortonormalne. Ponadto, ponieważ i są ukośne, dojeżdżają do pracy, skąd pokazuje, że nadal ma nieujemne wpisy. $A$

(U S)^{'} (U S) = S^{'} U^{'} U S = S^{'} I_{p} S = S^{'} S = S^{2} = I_{p}

$(US)^\prime(US) = S^\prime U^\prime U S = S^\prime I_p S = S^\prime S = S^2 = I_p$

U S

$US$

V S

$VS$

S

$S$

D

$D$

S D S = D S^{2} = D

$S D S = DS^2 = D$

D

$D$

Metoda zaimplementowana w kodzie w celu znalezienia SVD znajduje która przekątna i podobnie która przekątna Kontynuuje obliczanie w oparciu o wartości własne znalezione w . Problemem jest to nie zapewnia spójną dopasowanie kolumn z kolumnami . $U$

A A^{'} = (U D V^{'}) (U D V^{'})^{'} = U D V^{'} V D^{'} U^{'} = U D^{2} U^{'}

$AA^\prime = (UDV^\prime)(UDV^\prime)^\prime = UDV^\prime V D^\prime U^\prime = UD^2 U^\prime$

V

$V$

A^{'} A = V D^{2} V^{'} .

$A^\prime A = VD^2V^\prime.$

D

$D$

D^{2}

$D^2$ $U$ $V$

Rozwiązanie

Zamiast tego, po znalezieniu takiego i takiego , użyj ich do obliczenia $U$ $V$

U^{'} A V = U^{'} (U D V^{'}) V = (U^{'} U) D (V^{'} V) = D

$U^\prime A V = U^\prime (U D V^\prime) V = (U^\prime U) D (V^\prime V) = D$

bezpośrednio i skutecznie. Wartości diagonalne tego niekoniecznie są dodatnie. $D$ (Jest tak, ponieważ nie ma nic w procesie diagonalizacji lub który to zagwarantuje, ponieważ te dwa procesy zostały przeprowadzone osobno.) Ustaw je pozytywnie, wybierając wpisy wzdłuż przekątnej wyrównać znaki wpisów , aby miała wszystkie wartości dodatnie. Zrekompensuj to, mnożąc odpowiednio przez : $A^\prime A$ $AA^\prime$ $S$ $D$ $SD$ $U$ $S$

A = U D V^{'} = (U S) (S D) V^{'} .

$A = U D V^\prime = (US) (SD) V^\prime.$

To jest SVD.

Przykład

Niech z . SVD jest $n=p=k=1$ $A=(-2)$

(- 2) = (1) (2) (- 1)

$(-2) = (1)(2)(-1)$

z , i . $U=(1)$ $D=(2)$ $V=(-1)$

Jeśli przekątna naturalnie wybrałbyś i . Podobnie, jeśli przekątna , wybierzesz . Niestety, Zamiast tego oblicz Ponieważ jest to ujemne, ustaw . To dostosowuje do i do . Otrzymałeś który jest jednym z dwóch możliwych SVD (ale nie takim samym jak oryginał!). $A^\prime A = (4)$ $U=(1)$ $D=(\sqrt{4})=(2)$ $AA^\prime=(4)$ $V=(1)$

U D V^{'} = (1) (2) (1) = (2) \neq A .

$UDV^\prime = (1)(2)(1) = (2) \ne A.$

D = U^{'} A V = (1)^{'} (- 2) (1) = (- 2) .

$D=U^\prime A V = (1)^\prime (-2) (1) = (-2).$

S = (- 1)

$S=(-1)$

U

$U$

U S = (1) (- 1) = (- 1)

$US = (1)(-1)=(-1)$

D

$D$

S D = (- 1) (- 2) = (2)

$SD = (-1)(-2)=(2)$

A = (- 1) (2) (1),

$A = (-1)(2)(1),$

Kod

Oto zmodyfikowany kod. Jego wydajność potwierdza

Metoda odtwarza się mpoprawnie.
$U$ i nadal są ortonormalne. $V$
Ale wynik nie jest tym samym SVD zwróconym przez svd. (Oba są jednakowo ważne.)

m <- matrix(c(1,0,1,2,1,1,1,0,0),byrow=TRUE,nrow=3)

U <- eigen(tcrossprod(m))$vector
V <- eigen(crossprod(m))$vector
D <- diag(zapsmall(diag(t(U) %*% m %*% V)))
s <- diag(sign(diag(D)))  # Find the signs of the eigenvalues
U <- U %*% s              # Adjust the columns of U
D <- s %*% D              # Fix up D.  (D <- abs(D) would be more efficient.)

U1=svd(m)$u
V1=svd(m)$v
D1=diag(svd(m)$d,n,n)

zapsmall(U1 %*% D1 %*% t(V1)) # SVD
zapsmall(U %*% D %*% t(V))    # Hand-rolled SVD
zapsmall(crossprod(U))        # Check that U is orthonormal
zapsmall(tcrossprod(V))       # Check that V' is orthonormal

— Whuber
źródło

+1. To jest bardzo jasne. Dodam tylko, że w praktyce wystarczy obliczyć albo Ualbo V, a następnie, aby uzyskać inną matrycę poprzez pomnożenie A. W ten sposób wykonuje się tylko jedną (zamiast dwóch) eigend-kompozycje, a znaki wyjdą dobrze.

— ameba

@Amoeba Zgadza się: w duchu ręcznego obliczania SVD, które najwyraźniej jest ćwiczeniem edukacyjnym, nie zwraca się tutaj uwagi na wydajność.

— whuber

Dziękuję za miłą pomoc! Myślę, że rozumiem ten problem (w końcu).

— failedstatistician

@Federico Dziękuję za to przypomnienie. Masz całkowitą rację - domyślnie założyłem, że wszystkie wartości własne są odrębne, ponieważ w rzeczywistości jest to prawie na pewno w przypadku zastosowań statystycznych i człowiek nie ma zwyczaju rozważać dwuznaczności w „zdegenerowanych” przestrzeniach własnych.

— whuber

Masz rację, to tylko przypadek skrajny i rzeczywiście trudny. W pewnym sensie jest to kolejny przejaw tego samego problemu, który zarysowałeś w odpowiedzi, że ta metoda nie zapewnia „dopasowania” między kolumnami

U

$U$ i

V

$V$ . Obliczanie SVD, począwszy od kompozycji elektronicznych, jest wciąż doskonałym przykładem do nauki.

— Federico Poloni

Jak nakreśliłem w komentarzu do odpowiedzi @ whuber, ta metoda obliczania SVD nie działa dla każdej matrycy . Problem nie ogranicza się do znaków.

Problem polega na tym, że mogą występować powtarzające się wartości własne, w tym przypadku składająca się z osobna $A'A$ i $AA'$ nie jest wyjątkowy i nie wszystkie wybory $U$ i $V$ może być użyty do odzyskania współczynnika przekątnej SVD. Na przykład, jeśli weźmiesz dowolną nie przekątną macierz ortogonalną (powiedzmy, $A=\begin{bmatrix}3/5&4/5\\-4/5&3/5\end{bmatrix}$ ), następnie $AA'=A'A=I$ . Wśród wszystkich możliwych wyborów macierzy wektorów własnych $I$ , eigenwróci $U=V=I$ , więc w tym przypadku $U'AV=A$ nie jest przekątna.

Intuicyjnie jest to kolejny przejaw tego samego problemu, który zarysowuje @whuber, że musi istnieć „dopasowanie” między kolumnami $U$ i $V$ , a osobne obliczenie dwóch osobnych kompozycji nie gwarantuje tego.

Jeśli wszystkie liczby w liczbie pojedynczej $A$ są różne, wówczas skład eigend jest unikalny (aż do skalowania / znaków) i metoda działa. Uwaga: nadal nie jest dobrym pomysłem stosowanie go w kodzie produkcyjnym na komputerze z arytmetyką zmiennoprzecinkową, ponieważ podczas tworzenia produktów $A'A$ i $AA'$ obliczony wynik może być zaburzony o wielkość rzędu $\|A\|^2u$ , gdzie to precyzja maszyny. Jeśli wielkości pojedynczych wartości znacznie się różnią (z grubsza ponad ), jest to szkodliwe dla dokładności liczbowej najmniejszych. $u \approx 2\times 10^{-16}$ $10^{-8}$

Obliczanie SVD z dwóch eigend-kompozycji jest doskonałym przykładem uczenia się, ale w rzeczywistych aplikacjach zawsze używaj svdfunkcji R do obliczania dekompozycji liczby pojedynczej.

— Federico Poloni
źródło

Ten komentarz jest dobrą radą. Pamiętaj jednak, że ten wątek nie dotyczy właściwego sposobu obliczania SVD (i uważam, że nikt nie sprzeciwiłby się twojej rekomendacji). PO domyślnie przyjmuje, że to svddziała. Rzeczywiście używają go jako standardu do porównania obliczeń ręcznych, których celem jest sprawdzenie zrozumienia, a nie zamiana svdw jakikolwiek sposób.

— whuber

@whuber Prawidłowa obserwacja; Przeredagowałem ostatni akapit.

— Federico Poloni