Singular Value Decomposition (SVD)-handleiding

BE.400 / 7.548

Singular value decomposition neemt een rechthoekige matrix van genexpressiegegevens (gedefinieerd als A, waarbij A een n x p matrix is) waarin de n rijen de genen voorstellen, en de p kolommen de experimentele condities. De SVD-theorema luidt:

Anxp= Unxn Snxp VTpxp

Waar

UTU = Inxn

VTV = Ipx (d.w.z.U en V orthogonaal zijn)

Waar de kolommen van U de linkse singuliere vectoren zijn (gencoëfficiëntvectoren);S (dezelfde afmetingen als A) heeft singuliere waarden en is diagonaal (modusamplitudes); en VT heeft rijen die de rechtse singuliere vectoren zijn (expressieniveauvectoren). De SVD is een expansie van de oorspronkelijke gegevens in een coördinatensysteem waarin de covariantiematrix diagonaal is.

Berekening van de SVD bestaat uit het vinden van de eigenwaarden en eigenvectoren van AAT en ATA.De eigenvectoren van ATA vormen de kolommen van V, de eigenvectoren van AAT vormen de kolommen van U. Ook zijn de singuliere waarden in S de kwadraten van de eigenwaarden van AATof ATA. De singuliere waarden zijn de diagonaalwaarden van de S-matrix en zijn gerangschikt in afnemende volgorde. De singuliere waarden zijn altijd reele getallen. Als de matrix A een reële matrix is, dan zijn U en V ook reëel.

Om te begrijpen hoe de SVD opgelost moet worden, nemen we het voorbeeld van de matrix dat in Kuruvilla et al. werd gegeven:

In dit voorbeeld is de matrix een 4×2 matrix.We weten dat voor een n x n matrix W, een niet nul vector x de eigenvector van W is als:

W x = l x

Voor een of andere scalar l. De scalar l heet dan een eigenwaarde van A, en men zegt dat x een eigenvector van A is die overeenkomt met l.

Om dus de eigenwaarden van de bovenstaande entiteit te vinden, berekenen we de matrices AAT en ATA. Zoals eerder gezegd vormen de eigenvectoren van AAT de kolommen van U, zodat we de volgende analyse kunnen uitvoeren om U te vinden.

Nu we een nx n matrix hebben, kunnen we de eigenwaarden van de matrix W bepalen.

Sinds W x = l x dan is (W- lI) x = 0

Voor een unieke verzameling eigenwaarden moet de determinant van de matrix (W-lI) gelijk zijn aan nul. Uit de oplossing van de karakteristieke vergelijking, |W-lI|=0 verkrijgen we dus:

l=0, l=0; l = 15+Ö221.5 ~ 29.883; l = 15-Ö221.5 ~ 0.117 (vier eigenwaarden aangezien het een vierde degreepolynomiaal is). Deze waarde kan gebruikt worden om de eigenvector te bepalen die in de kolommen van U geplaatst kan worden. Zo bekomen we de volgende vergelijkingen:

19.883 x1 + 14 x2= 0

14 x1 + 9.883 x2 =0

x3 = 0

x4 = 0

Als we de eerste twee vergelijkingen vereenvoudigen, krijgen we een verhouding die de waarde van x1 met die van x2 in verband brengt. De waarden van x1 en x2 worden zo gekozen dat de elementen van de S de vierkantswortels van de eigenwaarden zijn. Dus een oplossing die voldoet aan bovenstaande vergelijkingx1 = -0.58 en x2 = 0.82 en x3 = x4 = 0 (dit is de tweede kolom van de Umatrix).

Substitueren we de andere eigenwaarde dan krijgen we:

-9.883×1 + 14 x2 = 0

14 x1 – 19.883 x2= 0

x3 = 0

x4 = 0

Dus een oplossing die voldoet aan dit geheel van vergelijkingen is x1 = 0.82 en x2 = -0.58 en x3 = x4 = 0 (dit is de eerste kolom van de U matrix). Door deze te combineren bekomen we:

Ook ATA vormt de kolommen van V zodat we een gelijkaardige analyse kunnen doen om de waarde van V te vinden.

en op dezelfde manier verkrijgen we de uitdrukking:

Finitief zoals eerder vermeld is de S de vierkantswortel van de eigenwaarden uit AATof ATA. en kan rechtstreeks worden verkregen waardoor we:

Merk op dat: s1 > s2 > s3 > … wat in de paper werd aangegeven door de figuur 4 van de Kuruvillapaper. In dat artikel werden de waarden zo berekend en genormaliseerd dat de hoogste singuliere waarde gelijk was aan 1.

Proof:

A=USVT en AT=VSUT

ATA = VSUTUSVT

ATA = VS2VT

ATAV = VS2

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