Singular Value Decomposition (SVD)tutorial

BE.400 / 7.548

Singular Value Decomposition nimmt eine rechteckige Matrix von Genexpressionsdaten (definiert als A, wobei A eine n x p-Matrix ist), in der die n Zeilen die Gene und die p Spalten die Versuchsbedingungen darstellen. Das SVD-Theorem besagt:

Anxp= Unxn Snxp VTpxp

Wo

UTU = Inxn

VTV = Ipxp (d.h..U und V sind orthogonal)

Wobei die Spalten von U die linken singulären Vektoren (Genkoeffizientenvektoren) sind;S (dieselben Dimensionen wie A) hat singuläre Werte und ist diagonal (Modusamplituden); und VT hat Zeilen, die die rechten singulären Vektoren (Expressionsniveauvektoren) sind. Die SVD stellt eine Expansion der ursprünglichen Daten in einem Koordinatensystem dar, in dem die Kovarianzmatrix diagonal ist.

Die Berechnung der SVD besteht aus der Ermittlung der Eigenwerte und Eigenvektoren von AAT und ATA.Die Eigenvektoren von ATA bilden die Spalten von V, die Eigenvektoren von AAT bilden die Spalten von U. Außerdem sind die Singulärwerte in S Quadratwurzeln der Eigenwerte von AAT oder ATA. Die Singulärwerte sind die Diagonaleinträge der S-Matrix und werden in absteigender Reihenfolge angeordnet. Die Singulärwerte sind immer reelle Zahlen. Wenn die Matrix A eine reelle Matrix ist, dann sind auch U und V reell.

Um zu verstehen, wie man die SVD löst, nehmen wir das Beispiel der Matrix aus Kuruvilla et al:

In diesem Beispiel ist die Matrix eine 4×2 Matrix.Wir wissen, dass für eine n x n-Matrix W ein Vektor x, der nicht Null ist, der Eigenvektor von W ist, wenn:

W x = l x

für einen Skalar l. Der Skalar l wird als Eigenwert von A bezeichnet, und x wird als Eigenvektor von A bezeichnet, der l entspricht.

Um die Eigenwerte der obigen Einheit zu finden, berechnen wir also die Matrizen AAT und ATA. Wie bereits erwähnt, bilden die Eigenvektoren von AAT die Spalten von U, so dass wir die folgende Analyse durchführen können, um U zu finden.

Nun, da wir eine nx n Matrix haben, können wir die Eigenwerte der Matrix W bestimmen.

Da W x = l x ist, ist (W- lI) x = 0

Für eine eindeutige Menge von Eigenwerten muss die Determinante der Matrix (W-lI) gleich Null sein. Aus der Lösung der Charakteristikumsgleichung, |W-lI|=0, ergibt sich also:

l=0, l=0; l = 15+Ö221.5 ~ 29.883; l = 15-Ö221.5 ~ 0.117 (vier Eigenwerte, da es sich um ein Polynom vierten Grades handelt). Dieser Wert kann verwendet werden, um den Eigenvektor zu bestimmen, der in die Spalten von U gesetzt werden kann. So erhalten wir die folgenden Gleichungen:

19.883 x1 + 14 x2= 0

14 x1 + 9.883 x2 = 0

x3 = 0

x4 = 0

Wenn wir die ersten beiden Gleichungen vereinfachen, erhalten wir ein Verhältnis, das den Wert von x1 zu x2 in Beziehung setzt. Die Werte von x1 und x2 werden so gewählt, dass die Elemente von S die Quadratwurzeln der Eigenwerte sind. Somit ist eine Lösung, die die obige Gleichung erfülltx1 = -0,58 und x2 = 0,82 und x3 = x4 = 0 (dies ist die zweite Spalte der Umatrix).

Setzt man den anderen Eigenwert ein, erhält man:

-9.883×1 + 14 x2 = 0

14 x1 – 19.883 x2= 0

x3 = 0

x4 = 0

Eine Lösung, die diesen Gleichungssatz erfüllt, ist also x1 = 0,82 und x2 = -0,58 und x3 = x4 = 0 (dies ist die erste Spalte der U-Matrix). Kombiniert man diese, erhält man:

Auch ATA bildet die Spalten von V, so dass man eine ähnliche Analyse durchführen kann, um den Wert von V zu finden.

und auf ähnliche Weise erhalten wir den Ausdruck:

Schließlich ist, wie bereits erwähnt, S die Quadratwurzel aus den Eigenwerten von AAT oder ATA. und kann direkt erhalten werden, was uns ergibt:

Beachte, dass: s1 > s2 > s3 > … das ist, was das Papier durch die Abbildung 4 des Kuruvillapapers andeutet. In diesem Papier wurden die Werte so berechnet und normalisiert, dass der höchste singuläre Wert gleich 1 war.

Beweis:

A=USVT und 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., und Van Loan, C.F. (1989) Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press).
• Greenberg, M. (2001) Differentialgleichungen & Lineare Algebra (Upper Saddle River, N.J. : Prentice Hall).
• Strang, G. (1998) Einführung in die lineare Algebra (Wellesley, MA : Wellesley-Cambridge Press).