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

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^\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^\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$

$$(US)^\prime(US) = S^\prime U^\prime U S = S^\prime I_p S = S^\prime S = S^2 = I_p$$ $US$$VS$$S$$D$ $$S D S = DS^2 = 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$

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

Rozwiązanie

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

$$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^\prime = (US) (SD) V^\prime.$$

To jest SVD.

Przykład

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

$$(-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)$

$$UDV^\prime = (1)(2)(1) = (2) \ne A.$$ $$D=U^\prime A V = (1)^\prime (-2) (1) = (-2).$$ $S=(-1)$$U$$US = (1)(-1)=(-1)$$D$$SD = (-1)(-2)=(2)$ $$A = (-1)(2)(1),$$

Kod

Oto zmodyfikowany kod. Jego wydajność potwierdza

1. Metoda odtwarza się mpoprawnie.
2. $U$ i nadal są ortonormalne.$V$
3. 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

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.