Singular Value Decomposition (SVD)tutorial

BE.400 / 7.548

Singular Value Decomposition tar en rektangulär matris av genuttrycksdata (definierad som A, där A är en n x p-matris) där de n raderna representerar generna, och de p-kolumnerna representerar försöksförhållandena. SVD-satsen lyder:

Anxp= Unxn Snxp VTpxp

Varifrån

UTU = Inxn

VTV = Ipxp (dvs.U och V är ortogonala)

Där kolumnerna i U är de vänstra singulära vektorerna (genkoefficientvektorer), S (samma dimensioner som A) har singulära värden och är diagonala (modusamplitud) och VT har rader som är de högra singulära vektorerna (uttrycksnivåvektorer). SVD representerar en expansion av de ursprungliga uppgifterna i ett koordinatsystem där kovariansmatrisen är diagonal.

Beräkningen av SVD består av att man hittar egenvärdena och egenvektorerna för AAT och ATA.Egenvektorerna för ATA utgör kolumnerna i V, och egenvektorerna för AAT utgör kolumnerna i U. Dessutom är de singulära värdena i S kvadratiska rotdelar av egenvärdena från AAT eller ATA. De singulära värdena är diagonalerna i S-matrisen och är ordnade i fallande ordning. De singulära värdena är alltid reella tal. Om matrisen A är en reell matris är U och V också reella.

För att förstå hur man löser SVD tar vi exemplet med den matris som tillhandahölls i Kuruvilla et al:

I det här exemplet är matrisen en 4×2-matris.Vi vet att för en n x n-matris W är en vektor x som inte är noll en egenvektor till W om:

W x = l x

För en viss skalär l. Skalären l kallas för ett egenvärde till A och x sägs vara en egenvektor till A som motsvarar l.

För att hitta egenvärdena till den ovan nämnda entiteten beräknar vi alltså matriserna AAT och ATA. Som tidigare nämnts utgör egenvektorerna i AAT kolumnerna i U, så vi kan göra följande analys för att hitta U.

När vi nu har en matris med n x n kan vi bestämma egenvärdena i matrisen W.

Då W x = l x så är (W- lI) x = 0

För att det ska finnas en unik uppsättning egenvärden till determinanten av matrisen (W-lI) måste den vara lika med noll. Från lösningen av karaktäristkvationen, |W-lI|=0 får vi således:

l=0, l=0; l = 15+Ö221,5 ~ 29,883; l = 15-Ö221,5 ~ 0,117 (fyra egenvärden eftersom det är ett fjärde graders polynom). Detta värde kan användas för att bestämma den egenvektor som kan placeras i kolumnerna i U. På så sätt får vi följande ekvationer:

19,883 x1 + 14 x2= 0

14 x1 + 9.883 x2 = 0

x3 = 0

x4 = 0

När vi förenklar de två första ekvationerna får vi ett förhållande som relaterar värdet av x1 till x2. Värdena för x1 och x2 väljs så att elementen i S är kvadratrötter till egenvärdena. En lösning som uppfyller ovanstående ekvation är såledesx1 = -0,58 och x2 = 0,82 och x3 = x4 = 0 (detta är den andra kolumnen i Umatrixen).

Substituerar vi det andra egenvärdet får vi:

-9,883×1 + 14 x2 = 0

14 x1 – 19.883 x2= 0

x3 = 0

x4 = 0

Därmed är en lösning som uppfyller denna uppsättning av ekvationer x1 = 0,82 och x2 = -0,58 och x3 = x4 = 0 (detta är den första kolumnen i U-matrisen). Genom att kombinera dessa får vi:

På samma sätt utgör ATA kolumnerna i V så vi kan göra en liknande analys för att hitta värdet på V.

och på samma sätt får vi uttrycket:

Slutligt är S, som tidigare nämnts, kvadratroten av egenvärdena från AAT eller ATA. och kan erhållas direkt vilket ger oss:

Notera att: s1 > s2 > s3 > … vilket är vad som angavs i figur 4 i Kuruvilapappret. I den artikeln beräknades och normaliserades värdena så att det högsta singulära värdet var lika med 1.

Bevis:

A=USVT och 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) Differential equations & Linear algebra (Upper Saddle River, N.J. : Prentice Hall).
• Strang, G. (1998) Introduction to linear algebra (Wellesley, MA : Wellesley-Cambridge Press).