SVD: Singulierewaardenontbinding

SVD, pseudoinverse en PCA: SVD, pseudoinverse en PCA

SVD: Singulierewaardenontbinding

De singulierewaardenontbinding of singulierewaardendecompositie van een matrix, afgekort als SVD, wordt veel gebruikt in de statistiek (bijvoorbeeld in principale componenten analyse en in kleinste kwadraten methode voor data regressie), signaalverwerking (bijvoorbeeld om ruis in een signaal te reduceren) en in nog meer disciplines, zoals beeldbewerking en aanverwante gebieden. In deze theorie pagina bespreken we alleen wat de singulierewaardenontbinding is en wat het heeft te maken met eigenwaarden, maar niet hoe de SVD te berekenen. In praktijk doe je de berekeningen toch met numerieke software.

We bekijken een ( $m\times n$ )-matrix $A$ . Dan is $A^{\top}\!A$ een symmetrische matrix, en volgens de spectraalstelling voor symmetrische matrices, diagonaliseerbaar met reële eigenwaarden. Maar in dit geval geldt nog meer:

De eigenwaarden van $A^{\top}\!A$ zijn niet-negatief.

Stel dat $\vec{v}$ een eigenvector van $A^{\top}\!A$ is bij de eigenwaarde $\lambda$ . We mogen aannemen dat $\lVert\vec{v}\rVert=1$ . Dan: $\begin{aligned} 0\le\lVert A\vec{v}\rVert^2 &= (A\vec{v})\boldsymbol{\cdot} (A\vec{v})= (A\vec{v})^{\top}\!A\vec{v}=\vec{v}^{\top}\!A^{\top}\!A\vec{v}\\ &= \vec{v}^{\top}\lambda \vec{v}=\lambda (\vec{v}\boldsymbol{\cdot}\vec{v})=\lambda \lVert\vec{v}\rVert^2=\lambda\end{aligned}$

Je kunt dus vierkantswortels van de eigenwaarden nemen.

Stel dat $A$ een ( $m\times n$ )-matrix is. Dan zijn de singuliere waarden van $A$ de vierkantswortels van de eigenwaarden van $A^{\top}\!A$ .
Singuliere waarden wordt gewoonlijk aangeduid met $\sigma_1,\ldots, \sigma_n$ en gerangschikt in dalende volgorde, d.w.z. $\sigma_1\ge \sigma_2\ge \cdots\ge\sigma_n$ .

Bereken exact de singuliere waarden van $A=\matrix{0 & 1 & -1 \\ -1 & 2 & -2 \\ }$ .

De matrix $A^{\top}A= \matrix{0 & -1 \\ 1 & 2 \\ -1 & -2 \\ } \matrix{0 & 1 & -1 \\ -1 & 2 & -2 \\ } = \matrix{1 & -2 & 2 \\ -2 & 5 & -5 \\ 2 & -5 & 5 \\ }$ heeft eigenwaarden $\lambda_{1}={{\sqrt{113}+11}\over{2}} , \lambda_{2}={{11- \sqrt{113}}\over{2}} , \lambda_{3}=0$ (reken dit zelf na).

De singuliere waarden van $A$ zijn dus: $\sigma_{1}={{\sqrt{\sqrt{113}+11}}\over{\sqrt{2}}} , \sigma _{2}={{\sqrt{11-\sqrt{113}}}\over{\sqrt{2}}} , \sigma_{3}=0$ .

Nieuw voorbeeld

Voordat we de singulierewaardenontbinding kunnen formuleren moeten we het begrip orthogonale matrix definiëren.

Een reële vierkante matrix $B$ is orthogonaal dan en slechts dan als $B^{\top}\!B=B\,B^{\top}=I$

De volgende eigenschappen van een matrix $B$ zijn equivalent:

$B$ is orthogonaal.
de rijen van $B$ hebben een lengte 1 en staan onderling loodrecht op elkaar ten opzichte van het standaard inproduct.
de kolommen van $B$ hebben een lengte 1 en staan onderling loodrecht op elkaar ten opzichte van het standaard inproduct.

Nu kunnen we de singulierewaardenontbinding op de volgende manier te formuleren.

Stel dat $A$ een ( $m\times n$ )-matrix is met rang $r$ en met singuliere waarden $\sigma_1\ge \sigma_2\ge\cdots\sigma_r\gt 0$ en $\sigma_{r+1}=\sigma_{r+2}=\cdots = \sigma_n=0$ . Dan is er een orthogonale ( $m\times m$ )-matrix $U$ , een orthogonale ( $n\times n$ )-matrix $V$ en een ( $m\times n$ )-matrix $\Sigma$ met de singuliere waarden op de hoofddiagonaal in aflopende volgorde en verder nullen, zodat $A=U\Sigma V^{\top}$ $\Sigma$ is uniek bepaald, maar de orthogonale matrices $U$ en $V$ niet.

Je kunt de ontbinding ook opschrijven met de eerste $r$ kolomvectoren $\vec{u}_1,\ldots,\vec{u}_r$ van de matrix $U$ en de eerste $r$ kolomvectoren $\vec{v}_1,\ldots,\vec{v}_r$ van de matrix $V$ . Dan: $A=U\Sigma V^{\top}=\sigma_1\vec{u}_1\vec{v}_1^{\top}+ \ldots + \sigma_r\vec{u}_r\vec{v}_r^{\top}$ Als $r<m$ en/of $r<n$ dan geeft dit een compactere beschrijving van de singuliere waarden ontbinding.

$A=\matrix{2 & 0 \\ 0 & -3}= \matrix{0 & 1\\ 1 & 0} \cdot \matrix{3 & 0 \\ 0 & 2}\cdot \matrix{0 & 1\\ -1 & 0}=U\Sigma V^{\top}$

$A=\matrix{1 & 1 \\ 1 & 0 \\ 0 & 1}= \matrix{\tfrac{1}{3}\sqrt{6} & 0 & -\tfrac{1}{3}\sqrt{3}\\ \tfrac{1}{6}\sqrt{6} & -\tfrac{1}{2}\sqrt{2} & \tfrac{1}{3}\sqrt{3} \\ \tfrac{1}{6}\sqrt{6} & \tfrac{1}{2}\sqrt{2} & \tfrac{1}{3}\sqrt{3}}\cdot \matrix{\sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0}\cdot \matrix{\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2} \\ -\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2}}=U\Sigma V^{\top}$ We hebben ook de volgende meer compacte ontbinding: $\begin{aligned}A=\matrix{1 & 1 \\ 1 & 0 \\ 0 & 1} &= \matrix{\tfrac{1}{3}\sqrt{6} & 0 \\ \tfrac{1}{6}\sqrt{6} & -\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{6}\sqrt{6} & \tfrac{1}{2}\sqrt{2}} \cdot \matrix{\sqrt{3} & 0 \\ 0 & 1 }\cdot \matrix{\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2} \\ -\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2}} \\ \\ &= \sqrt{3}\cdot \matrix{\tfrac{1}{3}\sqrt{6} \\ \tfrac{1}{6}\sqrt{6} \\ \tfrac{1}{6}\sqrt{6}}\cdot \matrix{\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{2}\sqrt{2}}^{\top}+ 1\cdot\matrix{0 \\ -\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{2}\sqrt{2}}\cdot \matrix{-\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{2}\sqrt{2}}^{\top}\end{aligned}$