Mengapa saya tidak bisa mendapatkan SVD X yang valid melalui dekomposisi nilai eigen dari XX 'dan X'X?

Saya mencoba melakukan SVD dengan tangan:

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)

Tetapi baris terakhir tidak mkembali. Mengapa? Tampaknya ada hubungannya dengan tanda-tanda vektor eigen ini ... Atau apakah saya salah memahami prosedur?

Analisis Masalah

SVD suatu matriks tidak pernah unik. Biarkan matriks memiliki dimensi dan biarkan SVD-nyan × $A$$n\times k$

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

untuk matriks dengan kolom ortonormal, diagonal matriks dengan entri non-negatif, dan matriks dengan kolom ortonormal.U p × p D k × p $n\times p$$U$$p\times p$$D$$k\times p$$V$

Sekarang pilih, secara sewenang-wenang , setiap diagonal matriks memiliki s di diagonal, sehingga adalah identity . KemudianS ± 1 S 2 = I p × p I $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$$

juga merupakan SVD dari karena menunjukkan bahwa memiliki kolom ortonormal dan perhitungan serupa menunjukkan memiliki kolom ortonormal. Selain itu, karena dan adalah diagonal, mereka berpindah-pindah, dari mana menunjukkan masih memiliki entri yang tidak negatif.( U S ) ′ ( U S ) = S ′ U ′ U S = S ′ I p S = S ′ S = S $A$ U S V

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

Metode yang diterapkan dalam kode untuk menemukan SVD menemukan yang mendiagonalisasi dan, juga, sebuah yang mendiagonalisasi Ini mulai menghitung dalam hal nilai eigen yang ditemukan dalam . Masalahnya adalah ini tidak menjamin pencocokan konsisten kolom dengan kolom .A A ′ = ( U D V ′ ) ( U D V ′ ) $U$ V A ′ A = V D 2 V ′ . D D 2 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$

Sebuah solusi

Alih-alih, setelah menemukan dan seperti itu , gunakan untuk menghitung$U$$V$

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

secara langsung dan efisien. Nilai-nilai diagonal ini tidak selalu positif. $D$ (Itu karena tidak ada apa-apa tentang proses mendiagonalisasi baik atau yang akan menjamin bahwa, karena kedua proses itu dilakukan secara terpisah.) Buat mereka positif dengan memilih entri di sepanjang diagonal untuk menyamakan tanda-tanda entri , sehingga memiliki semua nilai positif. Kompensasi untuk ini dengan mengalikan kanan dengan :$A^\prime A$$AA^\prime$$S$$D$$SD$$U$$S$

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

Itu adalah SVD.

Contoh

Misalkan dengan . SVD adalah$n=p=k=1$$A=(-2)$

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

dengan , , dan .$U=(1)$$D=(2)$$V=(-1)$

Jika Anda mendiagonalisasi Anda secara alami akan memilih dan . Demikian juga jika Anda mendiagonalisasi Anda akan memilih . Sayangnya, Sebaliknya, hitung Karena ini negatif, atur . Ini menyesuaikan ke dan ke . Anda telah memperoleh yang merupakan salah satu dari dua SVD yang mungkin (tetapi tidak sama dengan yang asli!).$A^\prime A = (4)$$U=(1)$AA′=(4)V=(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),$$

Kode

Berikut adalah kode yang dimodifikasi. Hasilnya menegaskan

1. Metode ini dibuat ulang mdengan benar.
2. $U$ dan benar-benar masih normal.$V$
3. Tetapi hasilnya bukan SVD yang sama dikembalikan oleh svd. (Keduanya sama-sama valid.)

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

Seperti yang saya uraikan dalam komentar ke jawaban @ whuber, metode ini untuk menghitung SVD tidak bekerja untuk setiap matriks . Masalahnya tidak terbatas pada tanda-tanda.

Masalahnya adalah bahwa mungkin ada nilai eigen yang berulang, dan dalam hal ini komposisi eigend dari dan tidak unik dan tidak semua pilihan dan dapat digunakan untuk mengambil faktor diagonal dari SVD. Misalnya, jika Anda mengambil matriks ortogonal non-diagonal (misalnya, ), maka . Di antara semua pilihan yang mungkin untuk matriks vektor eigen , akan mengembalikan , sehingga dalam hal ini tidak diagonal.A A ' U V A = [ 3 / 5 4 / 5 - 4 / 5 3 / 5 ] A A ' = $A'A$$AA'$$U$$V$$A=\begin{bmatrix}3/5&4/5\\-4/5&3/5\end{bmatrix}$$AA'=A'A=I$$I$eigen$U=V=I$$U'AV=A$

Secara intuitif, ini adalah manifestasi lain dari masalah yang sama yang menguraikan @whuber, bahwa harus ada "kecocokan" antara kolom dan , dan menghitung dua komposisi eigend secara terpisah tidak memastikannya.$U$$V$

Jika semua nilai singular berbeda, maka komposisi eigend unik (hingga skala / tanda) dan metode ini bekerja. Catatan: itu masih bukan ide yang baik untuk menggunakannya dalam kode produksi pada komputer dengan aritmatika floating point, karena ketika Anda membentuk produk dan hasil yang dihitung dapat terganggu oleh jumlah urutan , di mana adalah presisi mesin. Jika besarnya nilai singular sangat berbeda (lebih dari , kira-kira), ini merugikan akurasi numerik dari yang terkecil.A ′ A A A ′ ‖ A ‖ 2 u u ≈ 2 × 10 - 16 10 - $A$$A'A$$AA'$$\|A\|^2u$$u \approx 2\times 10^{-16}$$10^{-8}$

Komputasi SVD dari dua komposisi eigend adalah contoh pembelajaran yang bagus, tetapi dalam kehidupan nyata aplikasi selalu menggunakan svdfungsi R untuk menghitung dekomposisi nilai singular.