Apa intuisi di balik SVD?

Saya telah membaca tentang dekomposisi nilai singular (SVD). Di hampir semua buku teks disebutkan bahwa itu faktorisasi matriks menjadi tiga matriks dengan spesifikasi yang diberikan.

Tapi apa intuisi di balik pemisahan matriks dalam bentuk seperti itu? PCA dan algoritma lain untuk pengurangan dimensi adalah intuitif dalam arti bahwa algoritma memiliki properti visualisasi yang bagus tetapi dengan SVD bukan itu masalahnya.

$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$$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}$$

$X$

Kemudian baca gambar ini menjadi R dan dapatkan bagian matriks dari struktur yang dihasilkan, mungkin menggunakan perpustakaan pixmap.

---

Jika Anda menginginkan panduan langkah demi langkah tentang cara mereproduksi hasil, Anda dapat menemukan kode di sini .

---

Hitung 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])

menghasilkan dua gambar berikut:

Di sebelah kiri kita dapat dengan mudah melihat garis-garis vertikal / horizontal pada gambar peringkat-1.

$20$

Yang cukup menarik: kita melihat bagian-bagian dari gambar asli yang sulit direpresentasikan sebagai superposisi garis-garis vertikal / horizontal, sebagian besar rambut hidung diagonal dan beberapa tekstur, dan mata!

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

Biarkan (jadi mengkuantifikasi daya ledak dalam arah ). Misalkan vektor satuan didefinisikan sehingga Persamaan (2) dapat diekspresikan secara ringkas menggunakan notasi matriks sebagai mana adalah matriks yang kolom ke- adalah , adalah matriks yang Kolom th adalah , dan$\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$adalah matriks diagonal dengan entri diagonal ke- adalah . Matriks adalah ortogonal, sehingga kita dapat mengalikan kedua sisi (3) dengan untuk mendapatkan Tampaknya kita sekarang telah menurunkan SVD dengan hampir nol upaya. Sejauh ini tidak ada langkah yang sulit. Namun, bagian penting dari gambar itu hilang - kita belum tahu bahwa itu ortogonal.$n \times n$$i$$\sigma_i$$V$$V^T$ $$A = U \Sigma V^T.$$ $A$$U$

Inilah fakta penting, bagian yang hilang: ternyata ortogonal bagi : Saya mengklaim bahwa jika ini tidak benar, maka tidak akan optimal untuk masalah (1). Memang, jika (4) tidak puas, maka akan mungkin untuk meningkatkan dengan mengganggunya sedikit ke arah .$A v_1$$A v_2$

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

Misalkan (untuk kontradiksi) bahwa (4) tidak puas. Jika sedikit terganggu dalam arah ortogonal , norma tidak berubah (atau setidaknya, perubahan dalam norma dapat diabaikan). Ketika saya berjalan di permukaan bumi, jarak saya dari pusat bumi tidak berubah. Namun, ketika yang terganggu ke arah , vektor yang terganggu di non-orthogonal arah , dan perubahan norma adalah non-diabaikan . 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$dapat ditingkatkan dengan jumlah yang tidak dapat diabaikan. Ini berarti bahwa tidak optimal untuk masalah (1), yang merupakan kontradiksi. Saya suka argumen ini karena: 1) intuisi sangat jelas; 2) intuisi dapat dikonversi langsung menjadi bukti yang kuat.$v_1$

Argumen serupa menunjukkan bahwa adalah ortogonal untuk dan , dan seterusnya. Vektor adalah pasangan ortogonal. Ini berarti bahwa vektor satuan dapat dipilih untuk berpasangan orthogonal, yang berarti matriks atas adalah matriks ortogonal. Ini melengkapi penemuan kami tentang SVD.$A v_3$$A v_1$$A v_2$$A v_1, \ldots, A v_n$$u_1, \ldots, u_n$$U$

---

Untuk mengubah argumen intuitif di atas menjadi bukti yang kuat, kita harus menghadapi kenyataan bahwa jika terganggu dalam arah , vektor yang terganggu bukan benar-benar vektor satuan. (Normalnya adalah .) Untuk mendapatkan bukti yang kuat, tentukan Vektor benar-benar merupakan vektor satuan. Tetapi seperti yang Anda dapat dengan mudah menunjukkan, jika (4) tidak puas, maka untuk nilai cukup kecil kita memiliki (dengan asumsi bahwa tanda$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$dipilih dengan benar). Untuk menunjukkan ini, cukup periksa bahwa . Ini berarti bahwa tidak optimal untuk masalah (1), yang merupakan kontradiksi.$f'(0) \neq 0$$v_1$

(Omong-omong, saya sarankan membaca penjelasan Qiaochu Yuan tentang SVD di sini . Khususnya, lihat "Kunci lemma # 1", yang kita bahas di atas. Seperti yang dikatakan Qiaochu, kunci lemma # 1 adalah "hati teknis dekomposisi nilai singular ".)

Bung ambil satu jam sehari Anda dan saksikan kuliah ini: https://www.youtube.com/watch?v=EokL7E6o1AE

Pria ini super lurus ke depan, penting untuk tidak melewatkan semua itu karena semuanya datang bersama pada akhirnya. Bahkan jika itu mungkin tampak agak lambat di awal, dia mencoba untuk menjabarkan titik kritis, yang dia lakukan!

Saya akan meringkaskannya untuk Anda, daripada hanya memberi Anda tiga matriks yang dilakukan semua orang (karena itu membingungkan saya ketika saya membaca deskripsi lainnya). Dari mana matriks itu berasal dan mengapa kita mengaturnya seperti itu? Ceramahnya berhasil! Setiap matriks (pernah dalam sejarah everness) dapat dibangun dari matriks dasar dengan dimensi yang sama, lalu memutarnya, dan merentangkannya (ini adalah teorema dasar aljabar linier). Masing-masing dari tiga matriks yang orang lempar mewakili matriks awal (U), matriks penskalaan (sigma), dan matriks rotasi (V).

Matriks penskalaan menunjukkan kepada Anda vektor rotasi mana yang mendominasi, ini disebut nilai singular. Dekomposisi adalah penyelesaian untuk U, sigma, dan V.