Tekil Değer Ayrışımı (Singular Value Decomposition)

Yazan : Şadi Evren ŞEKER

Lineer Cebir (Linear Algebra) konusunda kullanılan ve reel veya kompleks matrisler üzerinde ayrıştırmaya yarayan önemli bir konudur.

Basitçe bir matrisi 3 parçaya ayırarak tutar ve bu üç parçayı kullanarak aynı matrisin yeniden elde edilmesini sağlar.

M = UΣV

U, vahid masfuf (üniter matris, unitary matrix) olmaktadır

V matrisi, M matrisinin birimdik (orthonormal) özelliklerini tutan matristir.

Σ matrisi ise bir köşegen matrisi olup (diagonal matrix) tekil değerleri (singular values) tutmaktadır.

Örnek (Selmirsel’in talebi üzerine ekliyorum)

Örneğin M matrisi olarak aşağıdaki matris verilmiş olsun.

M =

1.0000	2.0000	3.0000
4.0000	5.0000	6.0000
7.0000	8.0000	9.0000

Yukarıdaki bu matrisi, M = UΣV şeklinde çarpanlarına ayıracak ve buradan SVD değeri olan Σ matrisini bulacağız.

U =

-0.2148	0.8872	0.4082
-0.5206	0.2496	-0.8165
-0.8263	-0.3879	0.4082

Σ =

16.8481	0.0000	0.0000
0.0000	1.0684	0.0000
0.0000	0.0000	0.0000

V =

-0.4797	-0.7767	-0.4082
-0.5724	-0.0757	0.8165
-0.6651	0.6253	-0.4082

Yukarıda bulduğumuz bu 3 matrisi çarparsak M matrisi aşağıdaki şekilde , ilk beklediğimiz matris olarak geri bulunur:

U* Σ *V^T =

1.0000	2.0000	3.0000
4.0000	5.0000	6.0000
7.0000	8.0000	9.0000

Kodlama

Yukarıda verilen bu matrislerin bulunmasını algoritmik olarak ele alacak olursak, program yazılacak kadar basit bir halde düşünebilmemiz gerekir. SVD hesaplanırken aslında bulunan değer basitçe

M = UΣV değeridir . Bu değeri aşağıdaki şekilde parçalara ayırabiliriz:

M[i][j] şeklindeki iki boyutlu matri için :

= Σ_{i < k} U[i][k] * S[k][k] * V[j][k] // M = UΣV ayrımındaki 3 ayrı matris

Yukarıdaki bu eşitlikte S matrisini karekökünün karesi şeklinde yazabiliriz:

S[k][k] = sqrt(S[k][k]) * sqrt(S[k][k]) // bir matrisin karekökünün karesi kendisi olduğuna göre

= Σ_{i < k} U[i][k] * sqrt(S[k][k]) * sqrt(S[k][k]) * V[j][k]

Çarpma işlemlerinin öncelikleri eşit olduğu için sondaki ve baştaki çarpmalara öncelik verebiliriz:

= Σ_{i < k} (U[i][k] * sqrt(S[k][k])) * (sqrt(S[k][k]) * V[j][k])

S matrisimizin köşegensel (diagonal) bir matris olduğunu yani sadece köşegenindeki değerlerin bulunduğunu bunun dışındaki değerlerin 0 olduğunu hatırlarsak, çarpım işlemini aşağıdaki şekilde basitleştirebiliriz.

= (U[i] * sqrt(S_diag)^{^T}) * (V[j] * sqrt(S_diag)^{^T})^{^T}

Yukarıdaki denklemden faydalanarak tekil değer ayrışımını veren elemanlar aşağıdaki şekilde hesaplanabilir:

U[i] * sqrt(S_diag)^{^T}
= { U[i][0] * sqrt(S[0][0]),
U[i][1] * sqrt(S[1][1]),
…,
U[i][k] * sqrt(S[k][k]) }

Görüldüğü üzere S matrisindeki köşegen değerleri (S[n][n] gibi) U matrisindeki i. satırdaki değerler ile çarpılmıştır.

Burada sqrt fonksiyonu karekök belirtir ve bir matrisin karakökü ile kastedilen aslında matrisin elemanlarının teker teker karekökünün alınmış halidir. S matrisi diyagonal bir matris olduğu için bu elemanların kareköklerinin alınması yeterlidir.

Yukarıdaki son denklemi bulduktan sonra koda geçirmek için yapılması gereken yukarıdaki matrisi hesaplayan bir döngü yazmaktır.

« Birimdik Yöneyler (Orthonormal Vectors) | Kovaryans ve Korelasyon (Covariance Correlation) »

Yorumlar

Toplam 1 yorum var.

selmirsel | 06 Aug 2009, 03:02
kısa ve net bir açıklama. saat sabahın 3:00 sayenizde rahat uyuyacağım. ama açıklamalı bir örnek süper giderdi.

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Tekil Değer Ayrışımı (Singular Value Decomposition)' isimli yazı 29 Dec 2008 tarihinde, saat: 07:11 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 908 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, Yapay Sinir Ağları (Artificial Neural Networks) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar