Singulierewaardenontbinding

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

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

$A=U\Sigma V^{T}$

waarin:

• $U$ een $m\times m$-orthogonale matrix is: $U^{T}U=I$,
• $V$ een $n\times n$-orthogonale matrix: $V^{T}V=I$, en
• $\Sigma$ een $m\times n$-pseudo-diagonaalmatrix. De eerste $r$ elementen op de diagonaal zijn de singuliere waarden van $A$, die we noteren als $\Sigma _{ii}=\sigma _{i}$ met $\sigma _{1}\geq \sigma _{2}\geq \ldots \geq \sigma _{r}>0$; alle andere elementen van $\Sigma$ zijn nul.

De kolommen $U_{1},\ldots U_{m}$ van $U$ zijn de linker singuliere vectoren.

De kolommen $V_{1},\ldots V_{n}$ van $V$ zijn de rechter singuliere vectoren.

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

Verband met eigenwaarden

De matrix $A^{T}A$ is een reële $n\times n$-symmetrische matrix met dezelfde nulruimte als $A$, en heeft dus ook rang $r.$ Die kan worden ontbonden als:

$A^{T}A=V\Lambda V^{T}$

waarin $V$ een orthogonale $n\times n$-matrix is en $\Lambda$ een $n\times n$-diagonaalmatrix van rang $r$ met de eigenwaarden van $A^{T}A$ op de diagonaal. $A^{T}A$ is positief semi-definiet en van de eigenwaarden zijn er $r$ van de $n$ strikt positief: $\lambda _{1}\geq \lambda _{2}\geq \ldots \geq \lambda _{r}>0$; de andere ($\lambda _{r+1}\ldots \lambda _{n}$) zijn nul.

De singuliere waarden zijn de positieve vierkantswortels uit de strikt positieve eigenwaarden van $A^{T}A$:

$\sigma _{i}={\sqrt {\lambda _{i}}},i=1,2,\ldots ,r$

Bepaling van de SWO

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

• Bereken de vierkante matrix $A^{T}A$.
• 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},\ldots$ 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,\ldots ,r$

Deze kolommen vormen een orthonormaal stel. Ze kunnen aangevuld worden tot een orthonormaal stel van $m$ vectoren met de gram-schmidtmethode.

Rekenvoorbeeld

Gegeven de matrix

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

Hieruit volgt

$A^{T}A={\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^{T}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^{T}A-\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^{T}A-\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}{\tfrac {1}{\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}{\tfrac {1}{\sqrt {2}}}\\{\tfrac {1}{\sqrt {2}}}\end{bmatrix}}={\begin{bmatrix}{\tfrac {1}{\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}{\tfrac {1}{\sqrt {2}}}\\{\tfrac {-1}{\sqrt {2}}}\end{bmatrix}}={\begin{bmatrix}{\tfrac {2}{\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 ten slotte:

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

Numerieke berekening van de SWO

In de bovenstaande berekening werd de gram-schmidtmethode gebruikt bij de berekening van de eigenwaarden en eigenvectoren van de matrix $A^{T}A$. 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.

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.

Toepassingen

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

SWO 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.

SWO 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.

Bronnen

• Joos Vandewalle & Ronald Cools. Toegepaste algebra: Lineaire algebra en analytische meetkunde. Garant, Leuven/Apeldoorn, 1998. ISBN 9053507728
• Paul Larmuseau Voorbeeld van online SVD tool met recommender algoritm

Bronnen, noten en/of referenties