7 Matriisin approksimointi

Tämän kappaleen laatimisessa on käytetty apuna kirjan [2] kappaletta 6.5.1.

Matriisia voidaan approksimoida pienemmän asteen matriisilla. Ideana on löytää matriisin singulaariarvohajotelman avulla alemman asteen matriisi, joka on lähimpänä alkuperäistä matriisia. Ensin täytyy kuitenkin määritel-lä mitä tämä määritel-lähimpänä oleminen matriisien tapauksessa tarkoittaa. Mää-ritellään siis matriiseille käytettävä normi, jonka suhteen approksimointi tehdään. Matriisin approksimoinnissa käytetään niin sanottua Frobenius normia. Ennen Frobenius normin määrittelyä tarvitsemme kuitenkin mat-riiseille määritetyn sisätulon.

Määritelmä 7.1. OlkootA=[a_{i j}] jaB=[b_{i j}]m×nmatriiseja. Tällöin matriisi sisätuloa merkitäänh·,·ija

hA,Bi= Xm

i=1

Xn

j=1

a_{i j}b_{i j}.

Määritelmä 7.2. Olkoon A = [a_{i j}] m×n matriisi ja h·,·i avaruudenR^m×n matriisi sisätulo. Tällöin matriisinFrobenius normiamerkitäänk · k_Fja

kAk_F=(hA,Ai)^1/2 =









 Xm

i=1

Xn

j=1

a_{i j}²











1/2

.

Frobenius normin määritelmästä huomataan, että kAk_F = kA^Tk_F, sillä matriisinAtransponointi vaihtaa vain Frobenius normissa olevien alkioi-den summausjärjestystä.

Seuraavan lauseen mukaan alkuperäistä matriisiaApienemmän asteen matriisi X, joka minimoi normin kA−Xk_F, on aina olemassa. Lause on muotoiltu käyttäen apuna kirjan [2] kappaletta 6.5.

Lause 7.3. Olkoon A m×n matriisi, jonka aste on r ja0 <k<r. Lisäksi olkoon Mkaikkien niiden m×n matriisien joukko, joiden aste on korkeintaan k. Tällöin on olemassa matriisi X∈ M, jolle

kA−Xk_F≤ kA−Sk_F, kaikille S∈ M.

Todistus. Tämän lauseen todistus sivuutetaan tässä työssä.

Mikäli kuitenkin oletetaan, että tämä Lauseen 7.3 norminkA−Xk_F mi-nimoiva matriisiX on olemassa, niin tällöin kyseinen matriisiX voidaan löytää matriisin singulaariarvohajotelman avulla. Ennen tämän tuloksen esittelyä ja todistusta tarvitsemme kaksi Frobenius normiin liittyvää tulos-ta.

Lemma 7.4. Olkoon A m×n matriisi ja Q m×m ortogonaalinen matriisi. Tällöin kQAk_F=kAk_F.

Todistus. Tämän lemman todistukseen on käytetty apuna kirjan [2] Lauseen 6.5.2 todistusta. Olkoona₁,a2, . . . ,anmatriisinAsarakevektorit. MatriisiQ on ortogonaalinen, jolloin Lauseen 1.7 mukaan saadaan

kQAk²

F= Xm

i=1

Xn

j=1

(Qa_j)_i2

= Xn

j=1

Xm

i=1

(Qa_j)_i

2

= Xn

j=1

kQa_jk²

= Xn

j=1

ka_jk²

= Xm

i=1

Xn

j=1

a_{i j}²

=kAk²

F

Tällöin täytyy olla myöskQAk_F=kAk_F.

Lemman 7.4 avulla voimme muotoilla matriisin A Frobenius normin käyttäen matriisinAsingulaariarvoja.

Lause 7.5. Olkoon A m×n matriisi, jonka aste on r. Lisäksi olkoon UΣV^Tmatriisin A singulaariarvohajotelma jaσ1, σ2, . . . , σrsen positiiviset singulaariarvot. Tällöin

kAk_F=(σ12+σ22+· · ·+σr2)^1/2.

Todistus. Käytämme apuna jo aiemmin Määritelmän 7.2 yhteydessä todet-tua tietoa, jonka mukaan yleisesti matriisinSja sen transpoosinS^T Frobe-nius normi on sama. Lisäksi matriisinAsingulaariarvohajotelmassa olevat matriisitUjaV^T ovat ortogonaalisia, jolloin Lemman 7.4 nojalla

kAk_F=kUΣV^Tk_F

=kΣV^Tk_F

=k(ΣV^T)^Tk_F

=kVΣ^Tk_F

=kΣ^Tk_F

=kΣk_F

=(σ12+σ22+· · ·+σr2)^1/2.

Tarvitsemme vielä yhden apuloksen ennenkuin esittelemme tämän kap-paleen päätuloksen matriisin approksimoinnista. Seuraava aputulos liittyy matriisinAsingulaariarvohajotelmanUΣV^Tyleiseen muotoon ja siinä esiin-tyvään diagonaalimatriisiinΣ.

Lemma 7.6. Olkoon A m×n matriisi, jolla on esitykset A = UΣV^T ja A = SΛY^T, joissa matriisit U, V, S ja Y ovat ortogonaalisia, ja matriisitΣjaΛ ovat diagonaalimatriiseja. Tällöin matriisien Σ ja Λ diagonaalialkioiden neliöt ovat järjestystä lukuunottamatta samat.

Todistus. Nyt Lauseen 4.2 todistuksessa olevan yhtälön (10) mukaan esityk-sestäA=UΣV^Tsaadaan

AA^T =U(ΣΣ^T)U^T ja vastaavasti esityksestäA=SΛY^T saadaan

AA^T =S(ΛΛ^T)S^T.

MatriisiU on ortogonaalisena kääntyvä, joten matriisitAA^T ja ΣΣ^T ovat similaariset. Vastaavasti matriisiSon kääntyvä, joten matriisitAA^T jaΛΛ^T ovat similaariset. Tällöin Lemman 3.4 kohdan (i) nojalla diagonaalimatriisit ΣΣ^T jaΛΛ^T ovat similaariset.

Nyt Lemman 3.4 kohdan (iii) nojalla diagonaalimatriiseillaΣΣ^TjaΛΛ^T on algebralliset kertaluvut huomioiden samat ominaisarvot. Lemman 3.2 nojalla nämä ominaisarvot ovat diagonaalimatriiseille ΣΣ^T jaΛΛ^T niiden diagonaalialkiot. Siispä matriiseillaΣΣ^T jaΛΛ^T on järjestystä lukuunotta-matta samat diagonaalialkiot. Lisäksi nämä diagonaalialkiot ovat matriisien ΛjaΣdiagonaalialkioiden neliöt. Siispä matriisienΣjaΛ diagonaalialkioi-den neliöt ovat järjestystä lukuunottamatta samat.

Nyt voimme esitellä ja todistaa tuloksen, jonka mukaan Lauseen 7.3 norminkA−Xk_Fminimoiva matriisi Xvoidaan löytää matriisinA singu-laariarvohajotelman avulla.

Lause 7.7. Olkooon A m×n matriisi, jonka aste on r ja singulaariarvohajotelma UΣV^T. Olkoon lisäksiMjoukko, joka sisältää kaikki korkeintaan astetta k olevat m×n matriisit, missä0<k<r. Olkoon A⁰ =UΣ⁰V^T, missä

ja luvutσ1 ≥ . . .≥ σk > 0ovat ensimmäiset k kappaletta matriisin A singulaa-riarvoja. Tällöin A⁰ ∈ Mja

kA−A⁰k_F=(σ_k+1²+· · ·+σr2)^1/2≤ kA−Sk_F, kaikille S∈ M.

Todistus. Lauseen todistuksessa on käytetty apuna kirjan [2] Lauseen 6.5.3 todistusta. Näytetään aluksi, että

kA−A⁰k_F=(σ_k+1²+· · ·+σr2)^1/2.

Nyt matriisitUjaVovat ortogonaalisia, jolloin Lemman 7.4 nojalla kA−A⁰k_F=kUΣV^T−UΣ⁰V^Tk_F

(16)

=kU(Σ−Σ⁰)V^Tk_F

=k(Σ−Σ⁰)V^Tk_F

=k((Σ−Σ⁰)V^T)^Tk_F

=kV(Σ−Σ⁰)^Tk_F

=k(Σ−Σ⁰)^Tk_F

=k(Σ−Σ⁰)k_F

=(σ_k+1²+· · ·+σr2)^1/2. Lauseen 7.3 mukaan on olemassa matriisiX∈ M, jolle

kA−Xk_F≤ kA−Sk_F,

kaikilleS∈ M. MatriisinΣ⁰diagonaalialkiot ovat matriisinAnollasta poik-keavia singulaariarvoja. Tällöin nähdään, että matriisillaΣ⁰onkkappaletta lineaarisesti riippumattomia sarakevektoreita, jolloin matriisinΣ⁰aste onk.

Lisäksi matriisitUjaV^Tovat ortogonaalisina kääntyviä, jolloin Lauseen 3.7 nojalla matriisinA⁰ =UΣ⁰V^Taste onk. TällöinA⁰∈ Mja pätee

(17) kA−Xk_F≤ kA−A⁰k_F=(σ_k+1²+· · ·+σr2)^1/2. Riittää siis näyttää, että

(18) kA−Xk_F≥(σk+12+· · ·+σr2)^1/2.

Tällöin olisi kohtien (17) ja (18) nojallakA−A⁰k_F=kA−Xk_F, jolloin kA−A⁰k_F=kA−Xk_F≤ kA−Sk_F

kaikillaS∈ M, ja lause olisi todistettu.

OlkoonQΩP^TmatriisinXsingulaariarvohajotelma, missä

Tässä matriisinXaste on korkeintaank, joten joillakinjvoi ollaωj =0. Mää-ritelläänB=Q^TAP, jolloinA=QBP^T. MatriisitQjaPovat ortogonaalisia, joten vastaavasti kuin kohdassa (16) saadaan

kA−Xk_F=kQBP^T−QΩP^Tk_F

=kQ(B−Ω)P^Tk_F

=kB−Ωk_F.

Jaetaan matriisiBsamankokoisiin lohkoihin kuin matriisiΩ, jolloin

B=

MatriisienB₁₁jaB₁₂muodoista nähdään, että matriisilla B₁₁ B₁₂

0 0

!

on kor-keintaan k kappaletta lineaarisesti riippumattomia rivivektoreita. Tällöin Astelauseen 2.3 nojalla matriisin B11 B12

0 0

!

aste on korkeintaank. Lisäksi matriisitQjaP^T ovat ortogonaalisina kääntyviä, jolloin Lauseen 3.7 nojalla matriisinY= Q B₁₁ B₁₂

0 0

!

P^T aste on myös korkeintaank. Tällöin matriisi

Y∈ MjakB₁₂k²

F>0, jolloin saadaan kA−Yk²

Tämä ei kuitenkaan ole mahdollista, sillä matriisilleXpätee (20) kA−Xk_F≤ kA−Sk_F,

kaikilla S ∈ M eli erityisesti myös matriisille Y ∈ M. Siispä täytyy olla B₁₂=

0

.

MatriisienB₁₁ jaB₂₁ muodoista voidaan päätellä, että matriisilla B₁₁

0

B21

0

!

on korkeintaankkappaletta lineaarisesti riippumattomia sarakevektoreita.

Siispä matriisin B11

0

B₂₁

0

!

aste on korkeintaan k. Lisäksi matriisit Q ja P^T ovat ortogonaalisina kääntyviä, jolloin Lauseen 3.7 nojalla matriisinC = Q B₁₁

0

Vastaavalla perustelulla kuin kohdassa (20) saadaan, että täytyy ollaB₂₁ =

0

. Nyt siisB₁₂ =

0

jaB₂₁=

0

, joten yhtälöstä (19) saadaan

Näytetään seuraavana, ettäB₁₁= Ωk. Määritellään matriisi Z=Q B₁₁

0

0 0

! P^T.

Nyt matriisilla B₁₁

0 0 0

!

on korkeintaankkappaletta lineaarisesti riippumat-tomia sarakevektoreita, joten vastaavasti kuin matriisilleCvoidaan päätel-lä, että matriisinZaste on korkeintaank. TällöinZ∈ Mja saadaan

kA−Zk²

Vastaavalla perustelulla kuin kohdassa (20) nähdään, että ei voi ollakA− Zk²

F < kA−Xk²

F. Siispä täytyy ollakA−Zk²

F = kA−Xk²

F, joten täytyy olla kB₁₁−Ωkk²

Olkoon matriisin B₂₂ singulaariarvohajotelma U₁ΛV₁^T, jossa luvut λ1, . . . , λr−k ovat matriisin Λ nollasta poikkeavat diagonaalialkiot. Olkoot lisäksi matriisit

TällöinΛ =U^T₁B₂₂V₁ja matriisit lohkoittain kertomalla saadaan U₂^T(Q^TAP)V₂=U₂^TBV₂

Nyt tässä matriisitQU₂jaPV₂ovat ortogonaalisia. Tällöin matriisillaAon Lemman 7.6 muotoa olevat esityksetA=UΣV^TjaA=QU2 Ωk

0

0

Λ

!

(PV2)^T, joten matriisienΣja Ωk

0

0

Λ

!

diagonaalialkioiden neliöt ovat järjestystä lu-kuunottamatta samat. Tällöin voimme arvioida matriisinΛ diagonaalial-kioiden neliöiden summaaλ12+· · ·+λr−k2alaspäin matriisinΣpienimpien diagonaalialkioiden neliöiden summalla. Nämä matriisinΣpienimmät dia-gonaalialkiot ovat Lauseen 4.2 mukaanσk+1+· · ·+σr. Tällöin saadaan

kA−Xk_F=kB₂₂k_F

=kΛk_F

=(λ12+· · ·+λr−k2)^1/2

≥(σk+12+· · ·+σr2)^1/2.

In document Matriisin singulaariarvohajotelma (sivua 47-55)