Dekomposisi

Pengenalan eig dan svd untuk membedah matriks.

Daftar isi

Dekomposisi adalah pemfaktoran sebuah matriks menjadi komponen-komponen yang strukturnya lebih sederhana, sehingga sifat matriks tersebut dapat dibaca dari komponennya dan bukan dari tumpukan elemennya. Topik ini memperkenalkan dua fungsi dekomposisi NumPy yang paling sering digunakan, yaitu np.linalg.eig untuk nilai dan vektor eigen serta np.linalg.svd untuk nilai singular, lengkap dengan verifikasi rekonstruksinya. Kedua fungsi ini juga menjadi fondasi banyak metode data, antara lain analisis komponen utama dan pemampatan matriks.

Dekomposisi eigen dengan np.linalg.eig#

Dekomposisi eigen mencari pasangan nilai dan vektor yang memenuhi hubungan berikut, yaitu perkalian matriks dengan vektornya hanya meregangkan vektor tersebut sebesar faktor $\lambda$ tanpa mengubah arahnya.

A v = \lambda v

Fungsi np.linalg.eig(A) mengembalikan dua array, yaitu array nilai eigen (eigenvalue) dan array vektor eigen (eigenvector). Konvensi NumPy menempatkan vektor eigen ke-i pada kolom ke-i array kedua, sehingga pasangan yang benar diambil dengan indeks yang sama pada kedua keluaran.

python

import numpy as np

A = np.array([[2.0, 1.0],
              [1.0, 2.0]])
nilai, vektor = np.linalg.eig(A)
print(np.round(nilai, 4))
print(np.round(vektor, 4))

text Keluaran

[3. 1.]
[[ 0.7071 -0.7071]
 [ 0.7071  0.7071]]

Matriks contoh bersifat simetris, yaitu sama dengan transposnya, dan pilihan ini disengaja karena matriks simetris selalu menghasilkan nilai eigen bilangan real. Keluarannya menyatakan nilai eigen 3 dan 1, sedangkan dua kolom pada array kedua adalah vektor eigennya. Hubungan keduanya dapat diverifikasi dengan menghitung kedua sisi persamaan $A v = \lambda v$ secara terpisah.

python

import numpy as np

A = np.array([[2.0, 1.0],
              [1.0, 2.0]])
nilai, vektor = np.linalg.eig(A)
v0 = vektor[:, 0]
lam0 = nilai[0]
print(np.round(A @ v0, 4))
print(np.round(lam0 * v0, 4))
print(np.allclose(A @ v0, lam0 * v0))

text Keluaran

[2.1213 2.1213]
[2.1213 2.1213]
True

Kedua sisi menghasilkan vektor yang sama, sehingga pasangan nilai dan vektor eigen pada keluaran eig benar-benar memenuhi definisinya. Verifikasi satu pasangan seperti ini cukup murah dilakukan dan layak disertakan setiap kali hasil dekomposisi menjadi dasar perhitungan berikutnya.

Matriks simetris dan keluaran kompleks#

Pemilihan matriks simetris pada contoh sebelumnya bukan sekadar kesederhanaan angka. Secara matematis, matriks simetris dijamin memiliki seluruh nilai eigennya berupa bilangan real, sehingga keluaran eig mudah dibaca. Matriks umum tidak menikmati jaminan tersebut dan dapat menghasilkan nilai eigen bilangan kompleks, sebagaimana ditunjukkan contoh berikut.

python

import numpy as np

R = np.array([[0.0, -1.0],
              [1.0, 0.0]])
nilai, vektor = np.linalg.eig(R)
print(nilai)
print(nilai.dtype)

text Keluaran

[0.+1.j 0.-1.j]
complex128

Matriks R memutar setiap vektor sebesar 90 derajat, sehingga tidak ada arah yang hanya diregangkan olehnya dan nilai eigennya berpaling ke bilangan kompleks. Huruf j pada keluaran menandai bagian imajiner, dan tipe arraynya menjadi complex128 secara otomatis. Perilaku ini normal dan bukan error, tetapi perlu diantisipasi apabila kode berikutnya mengasumsikan nilai real, misalnya saat menyortir nilai eigen dari yang terbesar.

Nilai singular dengan np.linalg.svd#

Dekomposisi nilai singular (singular value decomposition, SVD) memfaktorkan setiap matriks, baik persegi maupun tidak, menjadi tiga komponen berikut.

A = U \, \Sigma \, V^{T}

Komponen U dan V berupa matriks yang kolom-kolomnya saling tegak lurus dengan panjang satu, sedangkan $\Sigma$ adalah matriks diagonal yang entrinya disebut nilai singular (singular value) dan tersusun menurun dari yang terbesar. Fungsi np.linalg.svd(A) mengembalikan U, vektor nilai singular s, dan transpos V yang disebut Vt. Nilai singular dikembalikan sebagai vektor satu dimensi, bukan matriks diagonal, sehingga penyusunan ulang $\Sigma$ dilakukan dengan np.diag.

python

import numpy as np

A = np.array([[1.0, 2.0],
              [2.0, 4.0]])
U, s, Vt = np.linalg.svd(A)
print(np.round(U, 4))
print(s)
print(np.round(Vt, 4))

text Keluaran

[[-0.4472 -0.8944]
 [-0.8944  0.4472]]
[5.00000000e+00 1.04061363e-16]
[[-0.4472 -0.8944]
 [-0.8944  0.4472]]

Matriks contoh berperingkat satu, sehingga secara matematis nilai singularnya adalah 5 dan 0. Keluaran memperlihatkan 5 dan angka sekitar $10^{-16}$ , dan selisih kecil itu adalah sisa pembulatan pecahan, bukan nilai yang berarti. Fenomena inilah yang membuat perbandingan dengan nol persis tidak dapat diandalkan pada hasil dekomposisi.

Rekonstruksi dan peringkat matriks#

Fungsi np.linalg.svd mengembalikan s sebagai array satu dimensi berisi nilai singular, bukan matriks diagonal, sehingga np.diag(s) dibutuhkan untuk menyusunnya kembali menjadi matriks sebelum dikalikan. Untuk A berukuran m kali n, s memuat k nilai dengan k = min(m, n). Pada contoh persegi 2 kali 2 berikut, U dan Vt masing-masing berukuran 2 kali 2 sementara s memuat 2 nilai, sehingga hasil perkaliannya kembali berukuran sama dengan A. Ketiganya direkonstruksi menjadi A melalui operator @, dan hasilnya dibandingkan dengan A menggunakan np.allclose.

python

import numpy as np

A = np.array([[1.0, 2.0],
              [2.0, 4.0]])
U, s, Vt = np.linalg.svd(A)
rekonstruksi = U @ np.diag(s) @ Vt
print(np.round(rekonstruksi, 4))
print(np.allclose(rekonstruksi, A))
print(np.sum(s > 1e-10))

text Keluaran

[[1. 2.]
 [2. 4.]]
True
1

Rekonstruksi mengembalikan A dengan setia, dan np.allclose menegaskannya. Baris ketiga menghitung peringkat (rank) matriks, yaitu banyaknya nilai singular yang melewati ambang kecil seperti $10^{-10}$ . Penggunaan ambang diperlukan karena nilai singular yang semestinya nol hampir tidak pernah bernilai nol persis pada aritmetika pecahan, sebagaimana terlihat pada bagian sebelumnya. Peringkat yang diperoleh dengan cara ini berguna untuk mendiagnosis data, misalnya mendeteksi kolom yang merupakan gabungan linear dari kolom lain. Karena nilai singular tersusun menurun, jumlah nilai yang melewati ambang sekaligus menunjukkan seberapa banyak arah data yang benar-benar membawa informasi.

Pemampatan dengan sebagian nilai singular#

Karena nilai singularnya tersusun menurun, SVD memberi cara memperkirakan A dengan sebagian komponennya. Apabila hanya suku terbesar yang dipertahankan, yaitu $s_0$ dikalikan kolom pertama U dan baris pertama Vt, hasilnya adalah perkiraan berperingkat satu yang terbaik untuk A. Perkalian kolom dengan baris semacam ini dihitung dengan np.outer.

python

import numpy as np

A = np.array([[1.0, 2.0],
              [3.0, 4.0]])
U, s, Vt = np.linalg.svd(A)
A1 = s[0] * np.outer(U[:, 0], Vt[0, :])
print(np.round(s, 4))
print(np.round(np.linalg.norm(A - A1), 4))
print(np.round(s[1], 4))

text Keluaran

[5.465 0.366]
0.366
0.366

Besar kesalahan perkiraan diukur dengan np.linalg.norm pada selisih A - A1, yaitu norma Frobenius yang mengakarkan jumlah kuadrat seluruh selisih elemen, dan nilainya sama persis dengan nilai singular yang dibuang. Kesetaraan ini bukan kebetulan, melainkan sifat optimum SVD, yaitu perkiraan berperingkat $k$ yang terbaik diperoleh dengan mempertahankan $k$ nilai singular terbesarnya. Sifat inilah yang menjadikan SVD fondasi pemampatan data dan analisis komponen utama (principal component analysis, PCA), di mana arah data yang paling bervariasi diambil dari komponen dengan nilai singular terbesar. Pada data besar, mempertahankan sebagian kecil nilai singular teratas sudah mewakili sebagian besar informasinya, sehingga penyimpanan dan perhitungan berikutnya menjadi jauh lebih ringan.

Ringkasan#

np.linalg.eig(A) mengembalikan nilai eigen beserta vektor eigennya sebagai kolom yang berpasangan melalui indeks yang sama, dan hubungan $A v = \lambda v$ dapat diverifikasi dengan np.allclose.
Matriks simetris menjamin nilai eigen berupa bilangan real, sedangkan matriks umum dapat menghasilkan keluaran complex128.
np.linalg.svd(A) mengembalikan U, nilai singular menurun s, dan Vt, sedangkan A direkonstruksi dengan U @ np.diag(s) @ Vt.
Peringkat matriks dihitung dari banyaknya nilai singular di atas ambang kecil, dan pemampatan diperoleh dengan mempertahankan nilai singular terbesar.

Referensi#

numpy.linalg.eig — NumPy — Dokumentasi resmi dekomposisi eigen, termasuk konvensi penempatan vektor eigennya.
numpy.linalg.svd — NumPy — Dokumentasi resmi dekomposisi nilai singular dan bentuk keluarannya.