Singulierewaardenontbinding

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De singulierewaardenontbinding (SWO; Engels: Singular Value Decomposition, SVD) is een belangrijk begrip uit de lineaire algebra en numerieke wiskunde. De singuliere waarden beschrijven eigenschappen van een willekeurige matrix, analoog aan de eigenwaarden van een vierkante matrix. De SWO wordt onder meer gebruikt bij de studie van lineaire afbeeldingen, het bepalen van normen van matrices, het berekenen van de veralgemeende inverse of pseudo-inverse van een willekeurige matrix en de kleinstekwadratenoplossing van een willekeurig stelsel van lineaire vergelijkingen.

Definitie[bewerken]

Stel A is een reële m-bij-n-matrix van rang r. A kan geschreven worden als het product van drie matrices:

A = U \Sigma V^T

waarin:

  • U een m-bij-m-orthogonale matrix is: U^TU = I,
  • V een n-bij-n-orthogonale matrix: V^TV = I, en
  • \Sigma een m-bij-n-pseudo-diagonaalmatrix. De eerste r elementen op de diagonaal zijn de singuliere waarden van A, die we noteren als \sigma_1, \sigma_2, \dots \sigma_r met  \sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_r  > 0; alle andere elementen van \Sigma zijn nul.

De kolommen U_1, \dots U_m van U zijn de linker singuliere vectoren.

De kolommen V_1, \dots V_n van V zijn de rechter singuliere vectoren.

De matrix \Sigma is uniek; V, U zijn dat echter niet.

Verband met eigenwaarden[bewerken]

De matrix A^TA is een reële n-bij-n-symmetrische matrix met dezelfde nulruimte als A, en heeft dus ook rang r. Die kan worden ontbonden als:

A^TA = V \Lambda V^T

waarin V een orthogonale n-bij-n-matrix is en  \Lambda een n-bij-n-diagonaalmatrix van rang r met de eigenwaarden van A^TA op de diagonaal. A^TA is positief semi-definiet en van de eigenwaarden zijn er r van de n strikt positief: \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_r > 0 ; 0 de andere (\lambda_{r+1} \dots \lambda_n) zijn nul.

De singuliere waarden zijn de positieve vierkantswortels uit de strikt positieve eigenwaarden van A^TA:

 \sigma_i = \sqrt{\lambda_i}, i = 1, 2, \dots r

Bepaling van de SWO[bewerken]

Het bovenstaande levert de volgende methode voor het bepalen van de singulierewaardenontbinding van een matrix A:

  • Bereken de vierkante matrix A^TA.
  • Bepaal de eigenwaarden daarvan en rangschik die van groot naar klein. De positieve vierkantswortels ervan zijn de singuliere waarden in de matrix \Sigma.
  • Vind genormeerde eigenvectoren V_1, V_2, ... met lengte 1, voor elke eigenwaarde. Dit zijn de kolommen van de matrix V.
  • De eerste r kolommen van U kan men berekenen met:
U_i = \frac{AV_i}{\sigma_i}, i = 1...r
Deze kolommen vormen een orthonormaal stel. Ze kunnen aangevuld worden tot een orthonormaal stel van m vectoren met de Gram-Schmidtmethode.

Rekenvoorbeeld[bewerken]

Gegeven de matrix


A = \begin{bmatrix}3 & -1\\
1&3 \\
1 & 1 \end{bmatrix}.

Hieruit volgt

A^TA =
\begin{bmatrix}3 & 1 & 1 \\
-1 & 3 & 1 
\end{bmatrix}
 \begin{bmatrix}3  & -1\\
1&3 \\
1 & 1 \end{bmatrix}
= \begin{bmatrix}11 & 1 \\
1 & 11 \end{bmatrix}.

De eigenwaarden van deze matrix volgen uit

\det(A-\lambda I) = \begin{vmatrix} 11 - \lambda & 1 \\  1 & 11-\lambda \end{vmatrix} = 0

Dit is de vierkantsvergelijking  (11-\lambda)^2 -1 = 0 met als wortels de eigenwaarden \lambda_1= 12, \lambda_2=10 .

De twee singuliere waarden van A zijn dus:

\sigma_1 = \sqrt{12}, \sigma_2=\sqrt{10} .

De eigenvector V_1 = {\begin{bmatrix}x_1 & x_2 \end{bmatrix}}^T behorend bij de grootste eigenwaarde, 12, volgt uit de matrixvergelijking

A^TA - \lambda_1 I = \begin{bmatrix}-1 & 1 \\ 1  & -1 \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}

Hiervoor kunnen we x_1 = 1, x_2 = 1 kiezen (deze vector is nog niet genormeerd).

Voor de tweede eigenwaarde, 10, geldt analoog:

A^TA - \lambda_2 I = \begin{bmatrix}1 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}

Hiervoor kunnen we x_1 = 1, x_2 = -1 kiezen; maar x_1 = -1, x_2 = 1 zou even goed zijn.

De matrix met als kolommen deze eigenvectoren:

\begin{bmatrix}1 & 1 \\1 & -1 \end{bmatrix}

moeten we nu herleiden naar een orthogonale matrix. Dat gebeurt met de Gram-Schmidtmethode toegepast op de kolomvectoren van deze matrix. In dit geval zijn de kolomvectoren reeds orthogonaal. Na normering krijgen we dus de matrix V:

V = \begin{bmatrix} \tfrac1 \sqrt 2 &  \tfrac 1 \sqrt 2 \\ \tfrac 1 \sqrt 2 &  \tfrac {-1} \sqrt 2 \end{bmatrix}.

De eerste twee kolommen van U zijn dan:

U_1 = \tfrac 1 \sqrt{12} \begin{bmatrix}3 & -1\\
1&3 \\
1 & 1 \end{bmatrix}
\begin{bmatrix}\tfrac1 \sqrt 2 \\ \tfrac1 \sqrt 2 \end{bmatrix}
=
\begin{bmatrix} \tfrac1 \sqrt 6 \\ \tfrac 2 \sqrt 6 \\ \tfrac 1 \sqrt 6 \end{bmatrix}

en

U_2 = \tfrac 1 \sqrt{10} \begin{bmatrix}3 & -1\\
1&3 \\
1 & 1 \end{bmatrix}
\begin{bmatrix}\tfrac1 \sqrt 2 \\ \tfrac {-1} \sqrt 2 \end{bmatrix}
=
\begin{bmatrix} \tfrac2 \sqrt 5 \\ \tfrac {-1} \sqrt 5 \\ 0 \end{bmatrix}

De derde kolom van U wordt dan:

U_3 = \begin{bmatrix} \tfrac {-1} \sqrt {30} \\ \tfrac {-2} \sqrt {30} \\ \tfrac 5 \sqrt {30} \end{bmatrix}

De volledige singulierewaardenontbinding van A is tenslotte:

\begin{bmatrix}3 & -1\\
1&3 \\
1 & 1 \end{bmatrix}
=
\begin{bmatrix} \tfrac1 \sqrt 6 &  \tfrac 2 \sqrt 5 & \tfrac {-1} \sqrt {30}  \\
 \tfrac 2 \sqrt 6 &  \tfrac {-1} \sqrt 5 & \tfrac {-2} \sqrt {30} \\
 \tfrac1 \sqrt 6 & 0 & \tfrac 5 \sqrt {30} \end{bmatrix}
\begin{bmatrix} \sqrt 12 & 0 \\
0 & \sqrt 10 \\
0 & 0 \end{bmatrix}
\begin{bmatrix}  \tfrac1 \sqrt 2 &  \tfrac 1 \sqrt 2 \\ \tfrac 1 \sqrt 2 &  \tfrac {-1} \sqrt 2 \end{bmatrix}.

Numerieke berekening van de SVO[bewerken]

In de bovenstaande berekening werd de Gram-Schmidtmethode gebruikt bij de berekening van de eigenwaarden en eigenvectoren van de matrix A^TA. Voor computerberekeningen met beperkte nauwkeurigheid is de Gram-Schmidtmethode echter niet geschikt. Ze is niet numeriek stabiel; door de opeenstapeling van afrondingsfouten zijn de berekende vectoren niet meer orthogonaal. In de jaren 1960 ontwikkelden Gene Golub en medewerkers numeriek stabiele algoritmen voor de berekeningen van de singulierewaardenontbinding.[1]

Voor de berekening van eigenwaarden of singuliere waarden van grote ijle matrices is het iteratieve Lanczos-algoritme (naar Cornelius Lanczos) geschikt. Dit algoritme wordt gebruikt in het softwarepakket SVDPACK.[2]

Toepassingen[bewerken]

De opeenvolgende singuliere waarden kan men interpreten als energieniveaus. Door enkel de grootste te selecteren verkrijgt men een vereenvoudigd empirisch model dat de onderliggende data goed beschrijft.

SVO wordt veel gebruikt in de statistiek, signaalverwerking, patroonherkenning en verwante sectoren. Met singuliere waarden kan men een reductie verkrijgen in de dimensie van een probleem en een verkleining van de tijd om het op te lossen. Een voorbeeld is biometrische gezichtsherkenning: een foto of beeld van een gezicht wordt voorgesteld als een matrix van een aantal beeldelementen of pixels, naargelang de beeldresolutie. De belangrijkste kenmerken en verhoudingen van zo een beeld moeten dan vergeleken worden met die uit een database van bestaande personen om degene te vinden die er het meeste op lijkt. In plaats hiervoor de volledige beeldmatrix te gebruiken, kan men met een beperkt aantal singuliere waarden werken, die de structuur van de originele gegevens weergeven. Met een Hidden Markov Model kan dan de meest gelijkende kandidaat gezocht worden.[3]

SVO wordt ook gebruikt om ruis uit een reeks meetwaarden te verwijderen. Het energieverschil tussen het nuttig signaal en de ruis uit zich in de singuliere waarden van een matrix die uit de meetwaarden wordt opgebouwd. De grootste singuliere waarden zijn het meest representatief; de kleinere waarden zijn te wijten aan ruis en kan men door nul vervangen. Dan kan men een signaal zonder ruis reconstrueren.[4]

Bronnen[bewerken]

Bronnen, noten en/of referenties