Subbagian 7.5.2 Masalah kuadrat terkecil
Masalah kuadrat terkecil, yang telah kita pelajari dalam
Subbab 6.5, muncul ketika kita menghadapi sistem linear tak konsisten
\(A\xvec=\bvec\text{.}\) Karena sistem tersebut tidak memiliki solusi, kita mencari vektor
\(\xvec\) yang meminimumkan jarak antara
\(\bvec\) dan
\(A\xvec\text{.}\) Dengan kata lain, kita mencari vektor
\(\xhat\text{,}\) yaitu solusi hampiran kuadrat terkecil, dengan menyelesaikan
\(A\xhat=\bhat\text{,}\) dengan
\(\bhat\) sebagai proyeksi ortogonal dari
\(\bvec\) ke ruang kolom
\(A\text{.}\)
Jika kita memiliki dekomposisi nilai singular
\(A=U\Sigma V^T\text{,}\) maka banyaknya nilai singular taknol
\(r\) menyatakan peringkat
\(A\text{,}\) dan
\(r\) kolom pertama
\(U\) membentuk basis ortonormal untuk
\(\col(A)\text{.}\) Basis ini dapat digunakan untuk memproyeksikan vektor ke
\(\col(A)\) dan dengan demikian menyelesaikan masalah kuadrat terkecil.
Sebelum menelaah hubungan ini lebih lanjut, kita akan memperkenalkan Sage sebagai alat untuk mengotomatiskan pembentukan dekomposisi nilai singular. Salah satu hal baru ialah kita perlu menyatakan bahwa matriks terdiri atas entri titik mengambang. Hal ini dilakukan dengan menyertakan
RDF dalam definisi matriks, seperti ditunjukkan pada sel berikut.
Kegiatan 7.5.2.
Perhatikan persamaan \(A\xvec=\bvec\text{,}\) dengan
\begin{equation*}
\begin{bmatrix}
1 \amp 0 \\
1 \amp 1 \\
1 \amp 2
\end{bmatrix}
\xvec = \threevec{-1}36
\end{equation*}
-
Tentukan dekomposisi nilai singular dari
\(A\) menggunakan sel Sage di bawah. Apa saja nilai singular
\(A\text{?}\)
-
Berapakah
\(r\text{,}\) yaitu peringkat
\(A\text{?}\) Bagaimana cara menentukan basis ortonormal untuk
\(\col(A)\text{?}\)
-
Bentuklah dekomposisi nilai singular tereduksi
\(U_r\Sigma_rV_r^T\) dengan menyusun: matriks
\(U_r\text{,}\) yang terdiri atas
\(r\) kolom pertama
\(U\text{;}\) matriks
\(V_r\text{,}\) yang terdiri atas
\(r\) kolom pertama
\(V\text{;}\) dan
\(\Sigma_r\text{,}\) yaitu matriks diagonal persegi
\(r\times r\text{.}\) Verifikasi bahwa
\(A=U_r\Sigma_r V_r^T\text{.}\)
Perlu diingat bahwa jika
B adalah matriks yang didefinisikan dalam Sage, maka
B.matrix_from_columns( list ) dan
B.matrix_from_rows( list ) dapat digunakan untuk mengambil kolom atau baris dari
B. Sebagai contoh,
B.matrix_from_rows([0,1,2]) menghasilkan matriks yang dibentuk dari tiga baris pertama
B.
-
Bagaimana dekomposisi nilai singular tereduksi memberikan matriks yang kolom-kolomnya merupakan basis ortonormal untuk
\(\col(A)\text{?}\)
-
Jelaskan mengapa solusi hampiran kuadrat terkecil \(\xhat\) memenuhi
\begin{equation*}
A\xhat = U_rU_r^T\bvec.
\end{equation*}
-
Berapakah hasil kali
\(V_rV_r^T\text{,}\) dan mengapa hasil kali tersebut memiliki bentuk ini?
-
Jelaskan mengapa
\begin{equation*}
\xhat = V_r\Sigma_r^{-1}U_r^T\bvec
\end{equation*}
merupakan solusi hampiran kuadrat terkecil, lalu gunakan bentuk ini untuk menentukan \(\xhat\text{.}\)
Aktivitas ini memperlihatkan kemampuan dekomposisi nilai singular dalam menentukan solusi hampiran kuadrat terkecil bagi persamaan
\(A\xvec = \bvec\text{.}\) Karena dekomposisi tersebut langsung memberikan basis ortonormal untuk
\(\col(A)\text{,}\) yang sebelumnya harus kita bentuk menggunakan proses Gram–Schmidt, kita dapat dengan mudah memproyeksikan
\(\bvec\) ke
\(\col(A)\) dan memperoleh bentuk sederhana bagi
\(\xhat\text{.}\)
Proposisi 7.5.1.
Jika \(A=U_r\Sigma_r V_r^T\) adalah dekomposisi nilai singular tereduksi dari \(A\text{,}\) maka solusi hampiran kuadrat terkecil untuk \(A\xvec=\bvec\) diberikan oleh
\begin{equation*}
\xhat = V_r\Sigma_r^{-1}U_r^T\bvec.
\end{equation*}
Jika kolom-kolom
\(A\) bebas linear, maka persamaan
\(A\xhat = \bhat\) hanya memiliki satu solusi, sehingga terdapat solusi hampiran kuadrat terkecil tunggal
\(\xhat\text{.}\) Jika tidak, bentuk dalam
Proposisi 7.5.1 menghasilkan solusi
\(A\xhat=\bhat\) yang memiliki panjang terkecil.
Matriks
\(A^+ = V_r\Sigma_r^{-1}U_r^T\) dikenal sebagai
pseudoinvers Moore–Penrose dari
\(A\text{.}\) Jika
\(A\) dapat dibalik, maka
\(A^{-1} = A^+\text{.}\)
Subbagian 7.5.3 Hampiran berperingkat \(k\)
Jika kita memiliki dekomposisi nilai singular suatu matriks
\(A\text{,}\) kita dapat membentuk barisan matriks
\(A_k\) yang menghampiri
\(A\) dengan ketelitian yang makin tinggi. Hal ini mungkin terasa akrab bagi mahasiswa kalkulus yang telah melihat bagaimana fungsi
\(f(x)\) dapat dihampiri oleh fungsi linear, fungsi kuadrat, dan seterusnya dengan ketelitian yang makin tinggi.
Kita mulai dengan matriks berperingkat \(r\text{,}\) yaitu \(A\text{,}\) beserta dekomposisi nilai singularnya \(A=U\Sigma V^T\text{.}\) Untuk membentuk matriks hampiran \(A_k\text{,}\) kita mempertahankan \(k\) nilai singular pertama dan mengubah nilai lainnya menjadi nol. Sebagai contoh, jika \(\Sigma = \begin{bmatrix}
22 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 14 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 3 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
\end{bmatrix}
\text{,}\) kita dapat membentuk matriks
\begin{equation*}
\Sigma^{(1)} = \begin{bmatrix}
22 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
\end{bmatrix}, \hspace{24pt}
\Sigma^{(2)} = \begin{bmatrix}
22 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 14 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \\
\end{bmatrix}
\end{equation*}
dan mendefinisikan \(A_1 = U\Sigma^{(1)}V^T\) serta \(A_2 =
U\Sigma^{(2)}V^T\text{.}\) Karena \(A_k\) mempunyai \(k\) nilai singular taknol, kita mengetahui bahwa \(\rank(A_k) = k\text{.}\) Bahkan, dalam pengertian tertentu, \(A_k\) merupakan matriks terdekat dengan \(A\) di antara semua matriks berperingkat \(k\text{.}\)
Kegiatan 7.5.3.
Perhatikan matriks \(A=U\Sigma V^T\text{,}\) dengan
\begin{align*}
\amp U = \begin{bmatrix}
\frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \\
\frac{1}{2} \amp \frac{1}{2} \amp -\frac{1}{2} \amp -\frac{1}{2} \\
\frac{1}{2} \amp -\frac{1}{2} \amp \frac{1}{2} \amp -\frac{1}{2} \\
\frac{1}{2} \amp -\frac{1}{2} \amp -\frac{1}{2} \amp \frac{1}{2} \\
\end{bmatrix},\hspace{10pt}
\Sigma = \begin{bmatrix}
500 \amp 0 \amp 0 \amp 0 \\
0 \amp 100 \amp 0 \amp 0 \\
0 \amp 0 \amp 20 \amp 0 \\
0 \amp 0 \amp 0 \amp 4
\end{bmatrix}\\
\amp V = \begin{bmatrix}
\frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \\
\frac{1}{2} \amp -\frac{1}{2} \amp -\frac{1}{2} \amp \frac{1}{2} \\
-\frac{1}{2} \amp -\frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \\
-\frac{1}{2} \amp \frac{1}{2} \amp -\frac{1}{2} \amp \frac{1}{2}
\end{bmatrix}
\end{align*}
Menjalankan sel berikut akan membuat matriks U, V, dan Sigma. Perhatikan bahwa perintah diagonal_matrix menyediakan cara yang praktis untuk membentuk matriks diagonal \(\Sigma\text{.}\)
-
Bentuklah matriks
\(A=U\Sigma V^T\text{.}\) Berapakah
\(\rank(A)\text{?}\)
-
Sekarang bentuklah matriks hampiran
\(A_1=U\Sigma^{(1)}
V^T\text{.}\) Berapakah
\(\rank(A_1)\text{?}\)
-
Tentukan galat dalam hampiran
\(A\approx A_1\) dengan menghitung
\(A-A_1\text{.}\)
-
Sekarang tentukan
\(A_2 = U\Sigma^{(2)} V^T\) beserta galat
\(A-A_2\text{.}\) Berapakah
\(\rank(A_2)\text{?}\)
-
Tentukan
\(A_3 = U\Sigma^{(3)} V^T\) beserta galat
\(A-A_3\text{.}\) Berapakah
\(\rank(A_3)\text{?}\)
-
Apa yang terjadi jika kita menghitung
\(A_4\text{?}\)
-
Apa yang Anda amati tentang galat
\(A-A_k\) ketika
\(k\) meningkat?
Dalam aktivitas ini, matriks hampiran
\(A_k\) berperingkat
\(k\) karena dekomposisi nilai singularnya memiliki
\(k\) nilai singular tak nol. Kemudian kita melihat bahwa selisih antara
\(A\) dan hampiran
\(A_k\) mengecil ketika
\(k\) meningkat, yang berarti barisan
\(A_k\) menghasilkan hampiran yang semakin baik ketika
\(k\) meningkat.
Cara lain untuk menyatakan \(A_k\) adalah dengan dekomposisi nilai singular tereduksi, sehingga \(A_k = U_k\Sigma_kV_k^T\text{,}\) dengan
\begin{equation*}
U_k = \begin{bmatrix}
\uvec_1 \amp \ldots \amp \uvec_k
\end{bmatrix},\hspace{10pt}
\Sigma_k = \begin{bmatrix}
\sigma_1 \amp 0 \amp \ldots \amp 0 \\
0 \amp \sigma_2 \amp \ldots \amp 0 \\
\vdots \amp \vdots \amp \ddots \amp \vdots \\
0 \amp 0 \amp \ldots \amp \sigma_k
\end{bmatrix},\hspace{10pt}
V_k = \begin{bmatrix}
\vvec_1 \amp \ldots \amp \vvec_k
\end{bmatrix}\text{.}
\end{equation*}
Perhatikan bahwa matriks berperingkat \(1\text{,}\) \(A_1\text{,}\) kemudian berbentuk \(A_1 = \uvec_1\begin{bmatrix}\sigma_1\end{bmatrix}
\vvec_1^T = \sigma_1\uvec_1\vvec_1^T\text{,}\) dan secara serupa kita dapat menulis:
\begin{align*}
A \approx A_1 \amp = \sigma_1\uvec_1\vvec_1^T\\
A \approx A_2 \amp = \sigma_1\uvec_1\vvec_1^T +
\sigma_2\uvec_2\vvec_2^T\\
A \approx A_3 \amp = \sigma_1\uvec_1\vvec_1^T +
\sigma_2\uvec_2\vvec_2^T +
\sigma_3\uvec_3\vvec_3^T\\
\vdots \amp\\
A = A_r \amp = \sigma_1\uvec_1\vvec_1^T +
\sigma_2\uvec_2\vvec_2^T +
\sigma_3\uvec_3\vvec_3^T +
\ldots +
\sigma_r\uvec_r\vvec_r^T\text{.}
\end{align*}
Untuk dua vektor
\(\uvec\) dan
\(\vvec\text{,}\) matriks
\(\uvec~\vvec^T\) disebut
hasil kali luar dari
\(\uvec\) dan
\(\vvec\text{.}\) (Hasil kali titik
\(\uvec\cdot\vvec=\uvec^T\vvec\) kadang-kadang disebut
hasil kali dalam.) Hasil kali luar selalu merupakan matriks berperingkat
\(1\text{;}\) jadi di atas kita melihat bagaimana
\(A_k\) diperoleh dengan menjumlahkan
\(k\) matriks berperingkat
\(1\text{,}\) yang masing-masing membawa kita selangkah lebih dekat ke matriks asal
\(A\text{.}\)
Subbagian 7.5.4 Analisis komponen utama
Dalam
Subbab 7.3, kita mempelajari analisis komponen utama sebagai teknik untuk mengurangi dimensi suatu himpunan data. Secara khusus, kita membentuk matriks kovarians
\(C\) dari matriks data terpusat dan melihat bahwa nilai eigen serta vektor eigen
\(C\) memberi tahu kita tentang varians himpunan data pada berbagai arah. Kita menyebut vektor-vektor eigen
\(C\) sebagai
komponen utama dan mendapati bahwa memproyeksikan data ke subruang yang ditentukan oleh beberapa komponen utama pertama sering memberi kita cara untuk memvisualisasikan himpunan data tersebut. Ketika kita menambahkan lebih banyak komponen utama, kita mempertahankan lebih banyak informasi tentang himpunan data asal. Hal ini terasa serupa dengan hampiran berperingkat
\(k\) yang baru saja kita lihat, jadi mari kita telusuri kaitannya.
Misalkan kita memiliki himpunan data dengan \(N\) titik, \(A\) menyatakan matriks data terpusat, \(A = U\Sigma V^T\) adalah suatu dekomposisi nilai singular, dan nilai-nilai singular \(A\) dinotasikan dengan \(\sigma_i\text{.}\) Maka matriks kovarians
\begin{equation*}
C = \frac1N AA^T = \frac1N (U\Sigma V^T) (U\Sigma V^T)^T =
U\left(\frac1N \Sigma \Sigma^T\right) U^T.
\end{equation*}
Perhatikan bahwa \(\frac1N \Sigma\Sigma^T\) adalah matriks diagonal yang entri diagonalnya \(\frac1N\sigma_i^2\text{.}\) Oleh karena itu, diperoleh bahwa
\begin{equation*}
C =
U\left(\frac1N \Sigma \Sigma^T\right) U^T
\end{equation*}
merupakan diagonalisasi ortogonal \(C\text{,}\) yang menunjukkan bahwa
-
komponen utama himpunan data, yaitu vektor-vektor eigen
\(C\text{,}\) diberikan oleh kolom-kolom
\(U\text{.}\) Dengan kata lain, vektor-vektor singular kiri
\(A\) adalah komponen utama himpunan data tersebut.
-
varians pada arah suatu komponen utama adalah nilai eigen \(C\) yang terkait, sehingga
\begin{equation*}
V_{\uvec_i} = \frac1N\sigma_i^2.
\end{equation*}
Kegiatan 7.5.4.
Mari kita tinjau kembali himpunan data iris yang kita pelajari dalam
Subbab 7.3. Ingat bahwa terdapat empat pengukuran untuk masing-masing dari 150 bunga iris dan setiap bunga iris termasuk dalam salah satu dari tiga spesies.
Mengevaluasi sel berikut akan memuat himpunan data dan mendefinisikan matriks data terpusat
\(A\) yang berukuran
\(4\times150\text{.}\)
-
Tentukan nilai-nilai singular
\(A\) menggunakan perintah
A.singular_values(), lalu gunakan nilai-nilai tersebut untuk menentukan varians
\(V_{\uvec_j}\) pada arah masing-masing dari empat komponen utama. Berapakah proporsi varians yang dipertahankan oleh dua komponen utama pertama?
-
Sekarang kita akan menulis matriks \(\Gamma = \Sigma
V^T\) sehingga \(A = U\Gamma\text{.}\) Misalkan suatu titik data terpusat, misalnya kolom ke-100 dari \(A\text{,}\) ditulis sebagai kombinasi linear komponen-komponen utama:
\begin{equation*}
\xvec = c_1\uvec_1+c_2\uvec_2+c_3\uvec_3+c_4\uvec_4.
\end{equation*}
Jelaskan mengapa \(\fourvec{c_1}{c_2}{c_3}{c_4}\text{,}\) vektor koordinat \(\xvec\) dalam basis komponen utama, muncul sebagai kolom ke-100 dari \(\Gamma\text{.}\)
-
Misalkan sekarang kita memproyeksikan titik data terpusat
\(\xvec\) ini secara ortogonal ke subruang yang direntang oleh dua komponen utama pertama,
\(\uvec_1\) dan
\(\uvec_2\text{.}\) Apa koordinat titik yang diproyeksikan dalam basis ini, dan bagaimana kita dapat menemukannya dalam matriks
\(\Gamma\text{?}\)
-
Sebagai alternatif, tinjau hampiran
\(A_2=U_2\Sigma_2V_2^T\) dari matriks data terpusat
\(A\text{.}\) Jelaskan mengapa kolom ke-100 dari
\(A_2\) menyatakan proyeksi
\(\xvec\) ke subruang dua dimensi yang direntang oleh dua komponen utama pertama,
\(\uvec_1\) dan
\(\uvec_2\text{.}\) Kemudian jelaskan mengapa koefisien dalam proyeksi itu,
\(c_1\uvec_1 + c_2\uvec_2\text{,}\) membentuk vektor dua dimensi
\(\twovec{c_1}{c_2}\) yang merupakan kolom ke-100 dari
\(\Gamma_2=\Sigma_2
V_2^T\text{.}\)
-
Sekarang kita telah melihat bahwa kolom-kolom
\(\Gamma_2 =
\Sigma_2 V_2^T\) membentuk koordinat titik-titik data terpusat yang diproyeksikan ke subruang dua dimensi yang direntang oleh
\(\uvec_1\) dan
\(\uvec_2\text{.}\) Dalam sel di bawah, tentukan suatu dekomposisi nilai singular
\(A\) dan gunakan dekomposisi tersebut untuk membentuk matriks
Gamma2. Ketika Anda mengevaluasi sel ini, Anda akan melihat plot titik-titik data terpusat yang diproyeksikan, serupa dengan yang kita buat dalam
Subbab 7.3.
Pada perjumpaan pertama kita dengan analisis komponen utama, kita memulai dengan matriks data terpusat
\(A\text{,}\) membentuk matriks kovarians
\(C\text{,}\) lalu menggunakan nilai eigen dan vektor eigen
\(C\) untuk memproyeksikan data terpusat ke subruang berdimensi lebih kecil. Dalam bagian ini, kita telah melihat bahwa dekomposisi nilai singular
\(A\) menyediakan jalur yang lebih langsung: vektor-vektor singular kiri
\(A\) membentuk komponen utama, dan matriks hampiran
\(A_k\) menyatakan titik-titik data yang diproyeksikan ke subruang yang direntang oleh
\(k\) komponen utama pertama. Koordinat suatu titik data terpusat yang diproyeksikan diberikan oleh kolom-kolom
\(\Gamma_k =
\Sigma_kV_k^T\text{.}\)
