Optimalizace

5. Pouzitı spektralnıho rozkladu v optimalizaci

Tom Werner, Tom Kroupa

FEL CVUT

Uloha na nejmensı stopu

Stopa

Stopa ctvercove matice A = [aij ] ∈ Rn×n je

tr A = a11 + · · ·+ ann

Vlastnosti:

• tr(A + B) = tr A + tr B

• tr(αA) = α tr A

• tr(AT ) = tr A

• tr(AB) = tr(BA) pro A ∈ Rm×n a B ∈ Rn×m

• tr A = λ1 + · · ·+ λn

Skalarnı soucin a norma matic:

〈A,B〉 = tr(ATB) =∑i,j

aijbij

‖A‖ = 〈A,A〉1/2 =(∑

i,j

a2ij

)1/2

1 / 20

Umluva

Pro symetrickou A ∈ Rn×n platı

A = VΛVT

pro nejake

V = [ v1 · · · vn ], VTV = I

Λ =

λ1

. . .

λn

Umluva

Dale budeme predpokladat

λ1 ≤ · · · ≤ λn.

2 / 20

Vlastnı cısla jako optimalizacnı uloha

Veta

Ulohamin xTAx

za podmınek xTx = 1

x ∈ Rn

ma optimum v x = v1 a jejı optimalnı hodnota je λ1.

Dukaz:

xT Ax = xT VΛVT x = yT Λy = λ1y21 + · · ·+ λny

2n

Protoze V je ortogonalnı, pro kazde x, y splnujıcı x = Vy platı

xT x = yT VT Vy = 1 ⇐⇒ yT y = 1.

Tedy uloha je ekvivalentnı uloze

min λ1y21 + · · ·+ λny

2n

za podmınek y21 + · · ·+ y2

n = 1

y1, . . . , yn ∈ ROptimum zjevne nastava pro y = (1, 0, . . . , 0) = e1, coz odpovıda x = Ve1 = v1 a yT Λy = λ1.

Poznamka: Uloha je ekvivalentnı uloze minx 6=0

xTAx

xTx(Rayleigh quotient).

3 / 20

Veta

Necht’ k ≤ n. Uloha

min xTAx

za podmınek xTx = 1

vT1 x = · · · = vT

k−1x = 0

x ∈ Rn

ma optimum v x = vk a optimalnı hodnota je λk .

Dukaz: Protoze vi = Vei , platı

vTi x = vTi Vy = 0 ⇐⇒ eTi y = yi = 0.

Tedy uloha je ekvivalentnı uloze

min λ1y21 + · · ·+ λny

2n

za podm. y21 + · · ·+ y2

n = 1

y1 = · · · = yk−1 = 0

y1, . . . , yn ∈ R

Optimum nastava pro y = ek , coz odpovıda x = Vek = vk .

4 / 20

Uloha na nejmensı stopu

Veta

Necht’ k ≤ n. Uloha

min xT1 Ax1 + · · ·+ xTk Axk

za podmınek x1, . . . , xk jsou ortonormalnı

x1, . . . , xk ∈ Rn

ma optimum v (x1, . . . , xk) = (v1, . . . , vk) a optimalnı hodnota je λ1 + · · ·+ λk .

Tato veta neplyne z minule vety! Dukaz je ve skriptech.

Ekvivalentnı formulace

min tr(XTAX)

za podmınek XTX = I

X ∈ Rn×k

Je-li [ x1 · · · xk ] = X, je

xT1 Ax1 + · · ·+ xTk Axk = tr(XTAX) = tr(XXTA) = tr(PA)

kde P je ortogonalnı projektor na podprostor span{x1, . . . , xk} = rng X.5 / 20

Prolozenı bodu podprostorem

Optimalnı prolozenı bodu podprostorem

Uloha: Prolozenı bodu podprostorem

Necht’ a1, . . . , an ∈ Rm a k ≤ m. Najdi podprostor dimenze k, ktery minimalizuje

soucet ctvercu vzdalenostı k bodum a1, . . . , an.

0

a3

a2 a1

aj

‖XTaj‖

rngY

rngX = (rngY)⊥

• Hledany podprostor je rng Y kde Y ∈ Rm×k .

• Jeho ortogonalnı doplnek je (rng Y)⊥ = rng X kde X ∈ Rm×(m−k) a XTX = I.

• Oznacıme-li A = [ a1 · · · an ] ∈ Rm×n, soucet ctvercu vzdalenostı v bodum je

‖XTa1‖2 + · · ·+ ‖XTan‖2 = ‖XTA‖2 = tr(XTAATX)

6 / 20

Resenı

min tr(XTAATX)

za podmınek XTX = I

X ∈ Rm×(m−k)

• Spocıtej spektralnı rozklad AAT = VΛVT .

• Rozdel matici V =[

X Y]∈ Rm×m na bloky X ∈ Rm×(m−k) a Y ∈ Rm×k .

• Sloupce Y tvorı ortonormalnı bazi hledaneho podprostoru.

• Sloupce X tvorı ortonormalnı bazi jeho ortogonalnıho doplnku.

• Optimalnı hodnota ulohy je λ1 + · · ·+ λm−k .

7 / 20

Ekvivalentnı formulace ulohy

Uloha: Nejblizsı matice nizsı hodnosti (low-rank approximation)

min ‖A− B‖2

za podmınek rank B ≤ k

B ∈ Rm×n

0

a3

a2

b3b2

a1

b1

aj

rngX = (rngY)⊥

rngY

‖aj − bj‖ = ‖XTaj‖bj = YYTaj

Tvrzenı

Tato uloha je ma stejnou opt. hodnotu jako uloha na prolozenı bodu

podprostorem. Jejı optimalnı resenı je B = YYTA.

Myslenka dukazu: Je-li B = [ b1 · · · bn ], pak ‖A− B‖2 = ‖a1 − b1‖2 + · · ·+ ‖an − bn‖2.

Body b1, . . . , bn lezı v podprostoru dimenze k, prave kdyz rank B = dim span{b1, . . . , bn} ≤ k.

Tedy optimalnı body bi jsou ortog. projekce bodu ai na podprostor span{b1, . . . , bn} ⊆ rng Y.8 / 20

Poznamka

Necht’ a1, . . . , an ∈ Rm a k ≤ m. Tyto dve ulohy jsou ekvivalentnı:

• Najdi podprostor dimenze k , ktery minimalizuje soucet ctvercu vzdalenostı k

bodum a1, . . . , an.

• Najdi podprostor dimenze k , ktery maximalizuje soucet ctvercu ortogonalnıch

projekcı bodu a1, . . . , an.

0

rngY

rngX = (rngY)⊥

a

b

c

aj

a = ‖XTaj‖, c = ‖aj‖, b2 = c2 − b2

Dale budeme pracovat s minimalizacnı verzı.9 / 20

Prokladame afinnım podprostorem

Tvrzenı

Necht’ a1, . . . , an ∈ Rm a k ≤ m. Afinnı podprostor dimenze k, ktery minimalizuje

soucet ctvercu vzalenostı k bodum a1, . . . , an, prochazı jejich tezistem

a = 1n (a1 + · · ·+ an).

Dukaz: Afinnı podprostor parametrizujeme jako

{ b ∈ Rm | XT (b− b0) = 0 }.

Protoze XT X = I, soucet ctvercu vzdalenostı bodu a1, . . . , an k podprostoru je

‖XT (a1 − b0)‖2 + · · ·+ ‖XT (an − b0)‖2.

To mame minimalizovat pres promenne X ∈ Rm×(m−k) a b0 ∈ Rm za podmınky XT X = I.

Kdyz X je konstanta, minimum pres b0 se nabyva pro b0 = a.

Prolozenı bodu afinnım podprostorem dimenze k ≤ n:

1. Zadane body posuneme tak, aby mely teziste v pocatku: ai := ai − a.

2. Posunute body prolozıme (linearnım) podprostorem dimenze k

3. Nalezeny podprostor posuneme o a.

10 / 20

Singularnı rozklad

Singularnı rozklad (Singular Value Decomposition, SVD)

Veta (o SVD)

Kazdou matici A ∈ Rm×n lze rozlozit jako

A = USVT = s1u1vT1 + · · ·+ spupvT

p

kde S ∈ Rm×n je diagonalnı, U ∈ Rm×m, UTU = I, V ∈ Rn×n, VTV = I.

• matice S ma p = min{m, n} diagonalnıch prvku (singularnı cısla)

s1 ≥ · · · ≥ sp ≥ 0

• sloupce u1, . . . ,um matice U jsou leve singularnı vektory

• sloupce v1, . . . , vm matice V jsou prave singularnı vektory

Verze SVD (vynech sloupce U,V odpovıdajıcı nulovym sing. cıslum):

• plne SVD: U ∈ Rm×m, S ∈ Rm×n, V ∈ Rn×n

• redukovane SVD: U ∈ Rm×p, S ∈ Rp×p, V ∈ Rn×p

• ‘rank-minimalnı’ SVD: U ∈ Rm×r , S ∈ Rr×r , V ∈ Rn×r

kde r = rank A = rank S ≤ p

11 / 20

Souvislost SVD se spektralnım rozkladem

Jestlize A = USVT , pak

ATA = VSTUTUSVT = VSTSVT

AAT = USVTVSTUT = USSTUT

Nenulova singularnı cısla matice A jsou odmocniny nenulovych vlastnıch cısel

matic ATA a AAT .

Dukaz existence ‘rank-minimalnıho’ SVD:

• Najdi S ∈ Rr×r a V ∈ Rn×r z ‘redukovaneho’ spektralnıho rozkladu AT A = VST SVT .

• Poloz U = AVS−1 ∈ Rm×r .

• Dokaz, ze UT U = I a A = USVT .

12 / 20

Nejblizsı maticı nizsı hodnosti z SVD

Zopakujme ulohu na nejblizsı matici nizsı hodnosti:

min ‖A− B‖2

za podmınek rank B ≤ k

B ∈ Rm×n

Veta (Eckart-Young)

Necht’ A = USVT . Matice hodnosti nejvyse k nejblizsı k matici A je

B = USkVT = s1u1vT1 + · · ·+ skukvT

k kde Sk =

[Ik 0

0 0

]S.

Myslenka dukazu: Spocıtej optimalnı Y ze spektralnıho rozkladu AAT a dosad’ do B = YYT A.

Vzdalenost k nejblizsı matici hodnosti ≤k :

‖A− B‖ = ‖USVT −USkVT‖ = ‖U(S− Sk)VT‖= ‖S− Sk‖= ‖(sk+1, . . . , sp)‖ = (s2

k+1 + · · ·+ s2p)1/2

(uz vlastne vıme z vety o nejmensı stope)13 / 20

Prıklad: Singularnı cısla matice 30× 30 hodnosti 30:

0 5 10 15 20 25 30

0

50

100

150

200

250

300

350

400

450

500

14 / 20

Pouzitı ulohy na prolozenı bodu

podprostorem / PCA

Opakovanı

Spektralnı rozklad AAT = VΛVT pro A = [ a1 · · · an ] ∈ Rm×n.

• Sloupce Y ∈ Rm×k matice V odpovıdajıcı k nejvetsım vlastnım cıslum tvorı

ortonormalnı bazi podprostoru dimenze k , ktery minimalizuje soucet ctvercu

vzdalenostı k bodum A

• Chyba prolozenı je soucet λ1 + · · ·+ λk−1 nejmensıch vlastnıch cısel.

• Ortog. projekce bodu ai na optimalnı podprostor je bj = YYTaj . Pisme

bj = Ycj , cj = YTaj

neboli

B = YC, C = YTA

Tedy sloupce matice C ∈ Rk×n jsou souradnice bodu B v ortonormalnı bazi Y.

Pouzitı:

• Komprese: Matice A ma mn prvku, matice Y,C dohromady (m + n)k prvku.

• Redukce dimenze: Body C majı mensı dimenzi nez body A.

• Visualizace: Pro k ≤ 3 si body C muzeme prohlednout.

• Rozpoznavanı: Body C casto vhodnejsı pro klasifikaci/shlukovanı/mining.

15 / 20

Prıklad: Vlastnı vektory matice AAT (= leve sing. vektory matice A)

A ∈ R2×1000, sing. cısla (1, 0.2) A ∈ R3×1000, sing. cısla (1, 0.4, 0.2)

16 / 20

Statisticky pohled: Principal Component Analysis (PCA)

• a1, . . . , an jsou vzorky nahodneho vektoru a.

• Empiricka strednı hodnota:

E[a] ≈ a = 1n (a1 + · · ·+ an) = 1

nA1

• Empiricka kovariancnı matice:

E[(a− E[a])(a− E[a])T ] ≈ 1

n

∑i

ai aTi =

1

nAA

T

kde ai = ai − a, A = [ a1 · · · an ]

Dekorelace: Kdyz AAT

= VΛVT , nahodny vektor VTa ma diagonalnı

kovariancnı matici (jeho slozky jsou nekorelovane).

17 / 20

Prıklad: Visualizace + rozpoznavanı datAverage consumption of food types in grams per person per week in the UK(https://setosa.io/ev/principal-component-analysis)

England N.Ireland Scotland Wales

Alcoholic drinks 375 135 458 475

Beverages 57 47 53 73

Carcase meat 245 267 242 227

Cereals 1472 1494 1462 1582

Cheese 105 66 103 103

Confectionery 54 41 62 64

Fats and oils 193 209 184 235

Fish 147 93 122 160

Fresh fruit 1102 674 957 1137

Fresh potatoes 720 1033 566 874

Fresh Veg 253 143 171 265

Other meat 685 586 750 803

Other Veg 488 355 418 570

Processed potatoes 198 187 220 203

Processed Veg 360 334 337 365

Soft drinks 1374 1506 1572 1256

Sugars 156 139 147 175

-400 -300 -200 -100 0 100 200 300 400

-400

-300

-200

-100

0

100

200

• 4 body v 17-rozmernem prostoru

• Odecteme teziste.

• Prolozıme podprostorem dimenze 2 a promıtneme body do nej.

• Zobrazıme souradnice bodu v ortonormalnı bazi v16, v17

18 / 20

Priblizne resenı preurcenych homogennıch linearnıch soustav

Kdy je homogennı linearnı soustava (A ∈ Rm×n)

Ax = 0

‘preurcena’?

• Ma vzdy trivialnı resenı x = 0, tedy minimalizovat ‖Ax‖2 nema smysl.

• Smysluplna formulace:

min ‖Ax‖2

za podmınek xTx = 1

x ∈ Rn

Resenı: vlastnı vektor ATA prıslusny nejmensımu vlastnımu cıslu.

• Obecnejsı formulace:

min ‖AX‖2

za podmınek XTX = I

X ∈ Rn×(n−k)

kde k je predem znama dimenze prostoru resenı soustavy Ax = 0.

19 / 20

Prıklad: Priblizne prolozenı bodu kuzeloseckou

Uloha: Najdi kuzelosecku, ktera minimalizuje soucet ctvercu vzdalenostı k danym

bodum (x1, y1), . . . , (xm, ym) ∈ R2.

• Kuzelosecka: Q(x , y) = ax2 + bxy + cy2 + dx + ey + f = 0

• Presne resenı velmi tezke.

• Priblizna formulace:

min Q(x1, y1)2 + · · ·+ Q(xm, ym)2

za podmınek a2 + b2 + c2 + d2 + e2 + f 2 = 1

a, b, c , d , e, f ∈ R

Tedy: minimalizuj ‖Aθ‖ za podmınky θTθ = 1 kde

A =

x21 x1y1 y2

1 x1 y1 1...

......

......

...

x2m xmym y2

m xm ym 1

θ = (a, b, c , d , e, f )

20 / 20