Singular Value Decomposition (SVD)tutorial

BE.400 / 7.548

Singularvalue decomposition prende una matrice rettangolare di dati di espressione genica (definita come A, dove A è una matrice n x p) in cui le n righe rappresentano i geni e le p colonne rappresentano le condizioni sperimentali. Il teorema SVD afferma:

Anxp= Unxn Snxp VTpxp

dove

UTU = Inxn

VTV = Ipxp (cioèU e V sono ortogonali)

dove le colonne di U sono i vettori singolari di sinistra (vettori di coefficienti genici); S (le stesse dimensioni di A) ha valori singolari ed è diagonale (modeamplitudes); e VT ha righe che sono i vettori singolari di destra (vettori di livello di espressione). La SVD rappresenta un’espansione dei dati originali in un sistema di coordinate in cui la matrice di covarianza è diagonale.

Il calcolo della SVD consiste nel trovare gli autovalori e gli autovettori di AAT e ATA.Gli autovettori di ATA costituiscono le colonne di V, gli autovettori di AAT costituiscono le colonne di U. Inoltre, i valori singolari in S sono radici quadrate degli autovalori di AAT o ATA. I valori singolari sono le diagonali della matrice S e sono disposti in ordine decrescente. I valori singolari sono sempre numeri reali. Se la matrice A è una matrice reale, allora anche U e V sono reali.

Per capire come risolvere la SVD, prendiamo l’esempio della matrice che è stato fornito in Kuruvilla et al:

In questo esempio la matrice è una matrice 4×2.Sappiamo che per una matrice n x n W, allora un vettore non nullo x è l’autovettore di W se:

W x = l x

per qualche scalare l. Lo scalare l è chiamato un autovalore di A, e x è detto essere un autovettore di A corrispondente a l.

Quindi per trovare gli autovalori dell’entità di cui sopra calcoliamo le matrici AAT e ATA. Come detto in precedenza, gli autovettori di AAT compongono le colonne di U, quindi possiamo fare la seguente analisi per trovare U.

Ora che abbiamo una matrice nx n possiamo determinare gli autovalori della matrice W.

Siccome W x = l x allora (W- lI) x = 0

Per un insieme unico di autovalori il determinante della matrice (W-lI) deve essere uguale a zero. Così dalla soluzione dell’equazione del carattere, |W-lI|=0 otteniamo:

l=0, l=0; l = 15+Ö221.5 ~ 29.883; l = 15-Ö221.5 ~ 0.117 (quattro autovalori poiché è un polinomio di quarto grado). Questo valore può essere usato per determinare l’autovettore che può essere collocato nelle colonne di U. Così otteniamo le seguenti equazioni:

19.883 x1 + 14 x2= 0

14 x1 + 9.883 x2 =0

x3 = 0

x4 = 0

Semplificando le prime due equazioni si ottiene un rapporto che mette in relazione il valore di x1 con x2. I valori di x1 e x2 sono scelti in modo che gli elementi di S siano le radici quadrate degli autovalori. Così una soluzione che soddisfa l’equazione precedentex1 = -0,58 e x2 = 0,82 e x3 = x4 = 0 (questa è la seconda colonna della matrice).

Sostituendo l’altro autovalore si ottiene:

-9,883×1 + 14 x2 = 0

14 x1 – 19.883 x2= 0

x3 = 0

x4 = 0

Quindi una soluzione che soddisfa questo insieme di equazioni è x1 = 0,82 e x2 = -0,58 e x3 = x4 = 0 (questa è la prima colonna della matrice U). Combinando queste si ottiene:

Similmente ATA compone le colonne di V quindi possiamo fare un’analisi simile per trovare il valore di V.

e analogamente otteniamo l’espressione:

Infine, come detto precedentemente, S è la radice quadrata degli autovalori di AAT o ATA. e può essere ottenuto direttamente dandoci:

Nota che: s1 > s2 > s3 > … che è quello che il documento indicava con la figura 4 del Kuruvillapaper. In quell’articolo i valori erano calcolati e normalizzati in modo che il valore singolare più alto fosse uguale a 1.

Prova:

A=USVT e AT=VSUT

ATA = VSUTUSVT

ATA = VS2VT

ATAV = VS2

• Alter O, Brown PO, Botstein D. (2000) Decomposizione del valore singolare per l’elaborazione e la modellazione dei dati di espressione a livello di genoma. Proc Natl Acad Sci U S A, 97, 10101-6.
• Golub, G.H., and Van Loan, C.F. (1989) Matrix Computations, 2nd ed. (Baltimora: Johns Hopkins University Press).
• Greenberg, M. (2001) Equazioni differenziali &Algebra lineare (Upper Saddle River, N.J. : Prentice Hall).
• Strang, G. (1998) Introduction to linear algebra (Wellesley, MA : Wellesley-Cambridge Press).