Singular Value Decomposition (SVD)tutorial

BE.400 / 7.548

Singular Value Decomposition bierze prostokątną macierz danych o ekspresji genów (zdefiniowaną jako A, gdzie A jest macierzą n x p), w której n wierszy reprezentuje geny, a p kolumn reprezentuje warunki eksperymentu. Twierdzenie SVD stwierdza:

Anxp= Unxn Snxp VTpxp

Gdzie

UTU = Inxn

VTV = Ipxp (tzn.U i V są ortogonalne)

Gdzie kolumny U są lewymi wektorami osobliwymi (wektory współczynników genów); S (te same wymiary co A) ma wartości osobliwe i jest diagonalne (modeamplitudes); a VT ma rzędy, które są prawymi wektorami osobliwymi (wektory poziomów ekspresji). SVD reprezentuje rozwinięcie pierwotnych danych w układzie współrzędnych, gdzie macierz kowariancji jest diagonalna.

Obliczanie SVD polega na znalezieniu wartości własnych i wektorów własnych AAT i ATA.Wektory własne ATA tworzą kolumny V , wektory własne AAT tworzą kolumny U. Również wartości własne w S są pierwiastkami kwadratowymi wartości własnych z AAT lub ATA. Wartości szczególne stanowią elementy diagonalne macierzy S i są ułożone w porządku malejącym. Wartości osobliwe są zawsze liczbami rzeczywistymi. Jeśli macierz A jest macierzą rzeczywistą, to U i V są również rzeczywiste.

Aby zrozumieć, jak rozwiązać SVD, weźmy przykład macierzy, który został podany w Kuruvilla et al:

W tym przykładzie macierz jest macierzą 4×2.Wiemy, że dla macierzy n x n W, niezerowy wektor x jest wektorem własnym W jeżeli:

W x = l x

Dla pewnego skalara l. Skalar l nazywamy wartością własną A, a x jest wektorem własnym A odpowiadającym l.

Więc, aby znaleźć wartości własne powyższej własności obliczamy macierze AAT i ATA. Jak już wcześniej wspomniano, wektory własne AAT tworzą kolumny U, więc możemy wykonać następującą analizę, aby znaleźć U.

Teraz, gdy mamy macierz nx n, możemy określić wartości własne macierzy W.

Skoro W x = l x to (W- lI) x = 0

Dla unikalnego zestawu wartości własnych wyznacznik macierzy (W-lI) musi być równy zero. Zatem z rozwiązania równania charakterystycznego, |W-lI|=0 otrzymujemy:

l=0, l=0; l = 15+Ö221.5 ~ 29.883; l = 15-Ö221.5 ~ 0.117 (cztery wartości własne, ponieważ jest to czwarty stopień wielomianu). Wartość ta może być użyta do wyznaczenia wektora własnego, który może być umieszczony w kolumnach U. Otrzymujemy więc następujące równania:

19.883 x1 + 14 x2= 0

14 x1 + 9.883 x2 =0

x3 = 0

x4 = 0

Upraszczając dwa pierwsze równania otrzymujemy stosunek, który odnosi wartość x1 do x2. Wartości x1 i x2 są tak dobrane, że pierwiastki S są pierwiastkami kwadratowymi wartości własnych. Tak więc rozwiązanie, które spełnia powyższe równaniex1 = -0,58 i x2 = 0,82 oraz x3 = x4 = 0 (jest to druga kolumna macierzy).

Substytuując drugą wartość własną otrzymujemy:

-9.883×1 + 14 x2 = 0

14 x1 – 19.883 x2= 0

x3 = 0

x4 = 0

Tak więc rozwiązaniem spełniającym ten układ nierówności jest x1 = 0,82 i x2 = -0,58 oraz x3 = x4 = 0 (jest to pierwsza kolumna macierzy U). Łącząc je otrzymujemy:

Podobnie ATA tworzy kolumny V, więc możemy przeprowadzić podobną analizę, aby znaleźć wartość V.

i podobnie otrzymujemy wyrażenie:

Wreszcie, jak wspomniano wcześniej, S jest pierwiastkiem kwadratowym wartości własnych z AAT lub ATA. i może być otrzymane bezpośrednio dając nam:

Zauważmy, że: s1 > s2 > s3 > … na co wskazywał rysunek 4 w pracy Kuruvillapaper. W tym artykule wartości zostały obliczone i znormalizowane tak, że najwyższa wartość osobliwa była równa 1.

Proof:

A=USVT and 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) Wprowadzenie do algebry liniowej (Wellesley, MA : Wellesley-Cambridge Press).