Apa itu SVD

Apa itu SVD#

Jika kamu punya sebuah matriks 𝐴 berukuran π‘š Γ— 𝑛 , maka:

\[ 𝐴=π‘ˆΞ£π‘‰π‘‡ \]

Dengan:

π‘ˆ : Matriks ortogonal ukuran π‘š Γ— π‘š β†’ menyimpan informasi arah (fitur) di ruang baris (left singular vectors)

Ξ£ : Matriks diagonal ukuran π‘š Γ— 𝑛 β†’ berisi singular values (nilai penting yang menyatakan bobot/kontribusi masing-masing fitur)

𝑉 𝑇 : Transpose dari matriks ortogonal 𝑉 ukuran 𝑛 Γ— 𝑛 β†’ menyimpan informasi arah (fitur) di ruang kolom (right singular vectors)

Kegunaan SVD#

Singular Value Decomposition (SVD) adalah sebuah teknik dalam aljabar linear yang sangat berguna dalam berbagai bidang seperti ilmu komputer, statistik, dan pembelajaran mesin. Secara umum, SVD digunakan untuk memecah sebuah matriks menjadi tiga komponen utama, yaitu matriks ortogonal π‘ˆ , matriks diagonal Ξ£ , dan transpos dari matriks ortogonal 𝑉 . Pemecahan ini memungkinkan kita untuk memahami struktur internal dari data yang diwakili oleh matriks tersebut.

Salah satu kegunaan utama SVD adalah untuk reduksi dimensi. Dalam bidang pembelajaran mesin, SVD sering digunakan dalam metode Principal Component Analysis (PCA) untuk mengurangi jumlah fitur dalam data tanpa kehilangan terlalu banyak informasi penting. Hal ini sangat membantu dalam mengatasi masalah overfitting serta mempercepat proses pelatihan model. Selain itu, SVD juga sangat berguna dalam bidang pengolahan bahasa alami, khususnya dalam teknik Latent Semantic Analysis (LSA) yang digunakan untuk menemukan hubungan tersembunyi antara kata-kata dan dokumen, seperti pada mesin pencari atau sistem rekomendasi.

Di bidang pengolahan citra, SVD dimanfaatkan untuk kompresi gambar. Dengan hanya mempertahankan beberapa nilai singular terbesar, gambar dapat disimpan dalam ukuran file yang lebih kecil tanpa kehilangan banyak kualitas visual. Selain itu, dalam konteks penyelesaian sistem persamaan linear, SVD sangat bermanfaat terutama untuk sistem yang tidak memiliki solusi unik, karena dapat memberikan solusi terbaik dalam pendekatan kuadrat terkecil (least squares). SVD juga berguna dalam deteksi anomali, dengan membantu memisahkan informasi penting dari noise atau outlier yang ada dalam data. Oleh karena itu, SVD menjadi alat analisis yang sangat penting dan serbaguna dalam dunia data modern.

Bagaimana formula SVD#

Singular Value Decomposition (SVD) adalah metode dalam aljabar linear untuk memecah suatu matriks 𝐴 menjadi tiga komponen matriks yang lebih sederhana. Tujuannya adalah untuk memahami struktur atau informasi yang terkandung dalam matriks tersebut, seperti pola dominan, dimensi utama, atau komponen tersembunyi.

Secara umum, SVD dapat dituliskan dengan rumus:

𝐴#

π‘ˆ Ξ£ 𝑉 𝑇

𝐴 adalah matriks asli berukuran π‘š Γ— 𝑛

π‘ˆ adalah matriks ortogonal berukuran π‘š Γ— π‘š , berisi left singular vectors

Ξ£ adalah matriks diagonal π‘š Γ— 𝑛 , berisi singular values

𝑉 𝑇adalah transpos dari matriks ortogonal 𝑉 , berukuran 𝑛 Γ— 𝑛 , berisi right singular vectors

Baik! Kita akan mengimplementasikan langkah-langkah SVD secara manual untuk matriks A berikut:

Soal:#

Misal matriks A:

\[\begin{split} A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \\ \end{bmatrix} \end{split}\]

Langkah 1: Hitung \(A^T A\) dan \(A A^T\)#

Karena \(A\) adalah matriks simetris \(2 \times 2\), maka \(A^T = A\).

\[\begin{split} A^T A = A A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \\ \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \\ \end{bmatrix} = \begin{bmatrix} 3Γ—3 + 1Γ—1 & 3Γ—1 + 1Γ—3 \\ 1Γ—3 + 3Γ—1 & 1Γ—1 + 3Γ—3 \\ \end{bmatrix} = \begin{bmatrix} 9 + 1 & 3 + 3 \\ 3 + 3 & 1 + 9 \\ \end{bmatrix} = \begin{bmatrix} 10 & 6 \\ 6 & 10 \\ \end{bmatrix} \end{split}\]

Langkah 2: Cari Eigenvalue dari \(A^T A\)#

Misal \(\lambda\) adalah eigenvalue, maka:

\[ \det(A^TA - \lambda I) = 0 \]
\[\begin{split} \begin{vmatrix} 10 - \lambda & 6 \\ 6 & 10 - \lambda \\ \end{vmatrix} = 0 \end{split}\]
\[ (10 - \lambda)^2 - 36 = 0 \Rightarrow (10 - \lambda)^2 = 36 \Rightarrow 10 - \lambda = \pm 6 \]
\[ \lambda_1 = 4,\quad \lambda_2 = 16 \]

Langkah 3: Hitung Singular Values#

\[ \sigma_i = \sqrt{\lambda_i} \Rightarrow \sigma_1 = \sqrt{16} = 4,\quad \sigma_2 = \sqrt{4} = 2 \]

Langkah 4: Cari V (eigenvector dari \(A^TA\))#

Gunakan \(A^TA = \begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix}\)

Untuk \(\lambda = 16\):#

\[\begin{split} (A^TA - 16I) v = 0 \Rightarrow \begin{bmatrix} -6 & 6 \\ 6 & -6 \\ \end{bmatrix} \Rightarrow v_1 = \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} \quad \text{(sebelum normalisasi)} \end{split}\]

Normalisasi:

\[\begin{split} v_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{split}\]

Untuk \(\lambda = 4\):#

\[\begin{split} (A^TA - 4I) v = 0 \Rightarrow \begin{bmatrix} 6 & 6 \\ 6 & 6 \\ \end{bmatrix} \Rightarrow v_2 = \begin{bmatrix} 1 \\ -1 \\ \end{bmatrix} \Rightarrow v_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \end{split}\]

Langkah 5: Bentuk \(\Sigma\) dan \(V\)#

\[\begin{split} \Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ \end{bmatrix}, \quad V = \left[ \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \right] = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} \end{split}\]

Langkah 6: Hitung \(U\) dengan rumus:#

\[ U_i = \frac{1}{\sigma_i} A v_i \]

Untuk \(\sigma_1 = 4\), \(v_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}\)#

\[\begin{split} u_1 = \frac{1}{4} A v_1 = \frac{1}{4} A \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \frac{1}{4\sqrt{2}} \begin{bmatrix} 3+1 \\ 1+3 \end{bmatrix} = \frac{1}{4\sqrt{2}} \begin{bmatrix} 4 \\ 4 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{split}\]

Untuk \(\sigma_2 = 2\), \(v_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}\)#

\[\begin{split} u_2 = \frac{1}{2} A v_2 = \frac{1}{2\sqrt{2}} \begin{bmatrix} 3 - 1 \\ 1 - 3 \end{bmatrix} = \frac{1}{2\sqrt{2}} \begin{bmatrix} 2 \\ -2 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \end{split}\]

Hasil Akhir SVD#

\[\begin{split} U = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix},\quad \Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ \end{bmatrix},\quad V^T = \left(\frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix}\right)^T \end{split}\]

Jika kamu mau, aku bisa bantu cek hasilnya di Python atau pakai numpy biar kamu bisa lihat hasilnya valid juga. Mau aku tunjukkan?

Perhitungan Manual Matriks 4x2#

Diketahui: $\( A = \begin{bmatrix} 3 & 7 \\ 2 & 5 \\ 4 & 3 \\ 1 & 1 \\ \end{bmatrix} \quad \text{(ukuran 4 Γ— 2)} \)$

Kita akan melakukan Singular Value Decomposition (SVD) terhadap matriks ini, yaitu:

\[ A = U \cdot \Sigma \cdot V^T \]

Langkah-Langkah Singkat (Manual Konsep)

  1. Hitung \(A^T A\)

Karena A adalah 4Γ—2, maka \(A^T\) adalah 2Γ—4, sehingga:

\[\begin{split} A^T A = \begin{bmatrix} 3 & 2 & 4 & 1 \\ 7 & 5 & 3 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 7 \\ 2 & 5 \\ 4 & 3 \\ 1 & 1 \\ \end{bmatrix} \end{split}\]

Kalikan baris Γ— kolom:

\[\begin{split} A^T A = \begin{bmatrix} 3^2 + 2^2 + 4^2 + 1^2 & 3Γ—7 + 2Γ—5 + 4Γ—3 + 1Γ—1 \\ 3Γ—7 + 2Γ—5 + 4Γ—3 + 1Γ—1 & 7^2 + 5^2 + 3^2 + 1^2 \\ \end{bmatrix} \end{split}\]

Hitung elemen-elemennya:

  • \(3^2 + 2^2 + 4^2 + 1^2 = 9 + 4 + 16 + 1 = 30\)

  • \(3Γ—7 + 2Γ—5 + 4Γ—3 + 1Γ—1 = 21 + 10 + 12 + 1 = 44\)

  • \(7^2 + 5^2 + 3^2 + 1^2 = 49 + 25 + 9 + 1 = 84\)

Jadi:

\[\begin{split} A^T A = \begin{bmatrix} 30 & 44 \\ 44 & 84 \\ \end{bmatrix} \end{split}\]

  1. Hitung eigenvalue dari \(A^T A\)

Cari \(\lambda\) dari:

\[\begin{split} \left| \begin{matrix} 30 - \lambda & 44 \\ 44 & 84 - \lambda \\ \end{matrix} \right| = 0 \end{split}\]
\[ (30 - \lambda)(84 - \lambda) - 44^2 = 0 \Rightarrow \lambda^2 - 114\lambda + (2520 - 1936) = 0 \Rightarrow \lambda^2 - 114\lambda + 584 = 0 \]

Gunakan rumus kuadrat:

\[ \lambda = \frac{114 \pm \sqrt{114^2 - 4 \cdot 584}}{2} = \frac{114 \pm \sqrt{12996 - 2336}}{2} = \frac{114 \pm \sqrt{10660}}{2} \]
\[ \sqrt{10660} \approx 103.25 \]
\[ \lambda_1 \approx \frac{114 + 103.25}{2} = 108.625, \quad \lambda_2 \approx \frac{114 - 103.25}{2} = 5.375 \]

  1. Cari singular values = akar dari eigenvalue:

\[ \sigma_1 = \sqrt{108.625} \approx 10.42, \quad \sigma_2 = \sqrt{5.375} \approx 2.32 \]

  1. Bangun matriks \(\Sigma\)

Karena A adalah 4Γ—2, maka \(\Sigma\) adalah 4Γ—2:

\[\begin{split} \Sigma = \begin{bmatrix} 10.42 & 0 \\ 0 & 2.32 \\ 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \end{split}\]

  1. Matriks \(V\) dan \(U\)

  • \(V\) berasal dari eigenvector \(A^T A\)

  • \(U = \frac{1}{\sigma_i} A v_i\)

Kesimpulan SVD:

\[ A_{4Γ—2} = U_{4Γ—4} \cdot \Sigma_{4Γ—2} \cdot V^T_{2Γ—2} \]

Dengan:

  • \(\Sigma = \begin{bmatrix} 10.42 & 0 \\ 0 & 2.32 \\ 0 & 0 \\ 0 & 0 \end{bmatrix}\)

  • \(V\): eigenvector dari \(A^T A\) $\( V^T = \begin{bmatrix} -0.488 & -0.873 \\ -0.873 & 0.488 \\ \end{bmatrix} \)$

Baris-barisnya adalah vektor eigen dari \(A^T A\)

  • \(U\): dihitung dari \(Av_i / \sigma_i\)

\[\begin{split} U = \begin{bmatrix} -0.727 & -0.345 & -0.574 & -0.153 \\ -0.512 & -0.300 & 0.792 & 0.139 \\ -0.439 & 0.874 & 0.082 & -0.195 \\ -0.131 & 0.166 & -0.190 & 0.959 \\ \end{bmatrix} \end{split}\]

Kolom-kolom \(U\) adalah vektor ortonormal yang membentang ruang kolom dari \(A\).

import numpy as np

# Matriks asli
A = np.array([
    [3, 7],
    [2, 5],
    [4, 3],
    [1, 1]
])

# SVD dengan NumPy
U, S, VT = np.linalg.svd(A)

print("Matrix A:")
print(A)
print("\nU:")
print(U)
print("\nSingular values (S):")
print(S)
print("\nV^T:")
print(VT)

# Bentuk S ke dalam bentuk matriks diagonal (Sigma)
Sigma = np.zeros_like(A, dtype=float)
np.fill_diagonal(Sigma, S)

print("\nSigma:")
print(Sigma)

# Perkalian kembali: U @ Sigma @ V^T
A_reconstructed = U @ Sigma @ VT

print("\nRekonstruksi A dari UΞ£V^T:")
print(A_reconstructed)

# Cek apakah hasilnya sama
print("\nApakah A sama dengan rekonstruksi? ", np.allclose(A, A_reconstructed))

Matrix A:
[[3 7]
 [2 5]
 [4 3]
 [1 1]]

U:
[[-0.72667296 -0.34526321 -0.57386797 -0.15302052]
 [-0.51235825 -0.300381    0.79239419  0.13918232]
 [-0.4386146   0.87355405  0.0817107  -0.19453511]
 [-0.13058586  0.16573437 -0.19002726  0.95883737]]

Singular values (S):
[10.42226645  2.31869834]

V^T:
[[-0.48835631 -0.87264432]
 [ 0.87264432 -0.48835631]]

Sigma:
[[10.42226645  0.        ]
 [ 0.          2.31869834]
 [ 0.          0.        ]
 [ 0.          0.        ]]

Rekonstruksi A dari UΞ£V^T:
[[3. 7.]
 [2. 5.]
 [4. 3.]
 [1. 1.]]

Apakah A sama dengan rekonstruksi?  True
Contents