Tutorial i singulær værdidekomposition (SVD)

BE.400 / 7.548

Singulær værdidekomposition tager en rektangulær matrix af genekspressionsdata (defineret som A, hvor A er en n x p matrix), hvor de n rækker repræsenterer generne, og de p kolonner repræsenterer forsøgsbetingelserne. SVD-sætningen siger:

Anxp= Unxn Snxp VTpxp

Hvor

UTU = Inxn

VTV = Ipxp (dvs.U og V er ortogonale)

Hvor kolonnerne i U er de venstre singulære vektorer (genkoefficientvektorer);S (samme dimensioner som A) har singulære værdier og er diagonal (modeamplitutter); og VT har rækker, der er de højre singulære vektorer (udtryksniveauvektorer). SVD repræsenterer en udvidelse af de oprindelige data i et koordinatsystem, hvor kovariansmatrixen er diagonal.

Beregningen af SVD består i at finde egenværdierne og egenvektorerne for AAT og ATA.ATA’s egenvektorer udgør kolonnerne i V, AAT’s egenvektorer udgør kolonnerne i U. Desuden er de singulære værdier i S kvadratrodsværdier af egenværdier fra AAT eller ATA. De singulære værdier er diagonaltallene i S-matrixen og er anbragt i faldende rækkefølge. De singulære værdier er altid reelle tal. Hvis matrixen A er en reel matrix, er Uog V også reelle.

For at forstå, hvordan man løser SVD, lad os tage eksemplet med den matrix, der blev givet i Kuruvilla et al:

I dette eksempel er matricen en 4×2 matrix.Vi ved, at for en n x n-matrix W er en vektor x, der ikke er nul, en egenvektor til W, hvis:

W x = l x

for en vis skalar l. Denne skalar l kaldes en egenværdi til A, og x siges at være en egenvektor til A svarende til l.

Så for at finde egenværdierne for ovenstående enhed beregner vi matricerne AAT og ATA. Som tidligere nævnt udgør egenvektorerne i AAT kolonnerne i U, så vi kan foretage følgende analyse for at finde U.

Nu, hvor vi har en nx n-matrix, kan vi bestemme egenværdierne i matricen W.

Da W x = l x så er (W- lI) x = 0

For et unikt sæt af egenværdier til determinanten af matricen (W-lI) skal være lig med nul. Af løsningen af karakteristicekvationen |W-lI|=0 fås således:

l=0, l=0; l = 15+Ö221,5 ~ 29,883; l = 15-Ö221,5 ~ 0,117 (fire egenværdier, da der er tale om et fjerdegradspolynomium). Denne værdi kan bruges til at bestemme den egenvektor, der kan placeres i kolonnerne i U. Vi får således følgende ligninger:

19,883 x1 + 14 x2= 0

14 x1 + 9.883 x2 =0

x3 = 0

x4 = 0

Når vi forenkler de to første ligninger, får vi et forhold, der relaterer værdien af x1 til x2. Værdierne af x1 og x2 er valgt således, at elementerne i S er kvadratrødderne af egenværdierne. En løsning, der opfylder ovenstående ligning, er såledesx1 = -0,58 og x2 = 0,82 og x3 = x4 = 0 (dette er den anden kolonne i Umatrixen).

Substituerer vi den anden egenværdi, får vi:

-9,883×1 + 14 x2 = 0

14 x1 – 19.883 x2= 0

x3 = 0

x4 = 0

Sådan er en løsning, der opfylder dette sæt af ligninger, x1 = 0,82 og x2 = -0,58 og x3 = x4 = 0 (dette er den første kolonne i U-matrixen). Ved at kombinere disse får vi:

Sådan udgør ATA kolonnerne i V, så vi kan foretage en lignende analyse for at finde værdien af V.

og på samme måde får vi udtrykket:

Sidst som tidligere nævnt er S kvadratroden af egenværdierne fra AATeller ATA. og kan fås direkte, hvilket giver os:

Bemærk, at: s1 > s2 > s3 > … hvilket er hvad papiret indikerede ved figur 4 i Kuruvilpapiret. I dette papir blev værdierne beregnet og normaliseret således, at den højeste singulære værdi var lig med 1.

Bevis:

A=USVT og AT=VSUT

ATA = VSUTUSVT

ATA = VSUTUSVT

ATAV = VS2VT

ATAV = VS2

• Alter O, Brown PO, Botstein D. (2000) Singular value decomposition for genome-wide expression data processing and modelling. Proc Natl Acad Sci U S A, 97, 10101-6.
• Golub, G.H., og Van Loan, C.F. (1989) Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press).
• Greenberg, M. (2001) Differential equations & Linear algebra (Upper Saddle River, N.J. : Prentice Hall).
• Strang, G. (1998) Introduction to linear algebra (Wellesley, MA : Wellesley-Cambridge Press).