7.1 Singulærverdidekomposisjon A=UΣVᵀ

En singulærverdi til en matrise $A$ er kvadratroten av en egenverdi til $A^{T}A$: $\sigma_i=\sqrt{\lambda_i}$, der $\lambda_i\ge0$ er egenverdiene til den symmetriske matrisen $A^{T}A$. Singulærverdiene er alltid $\ge0$ og ordnes synkende, $\sigma_1\ge\sigma_2\ge\dots$ Til forskjell fra egenverdiene til $A$ (som kan være negative eller komplekse) er singulærverdiene reelle og ikke-negative — de måler hvor mye $A$ strekker i hver hovedretning.

Matrisen $A^{T}A$ er hjørnesteinen i SVD fordi den alltid er symmetrisk ($(A^{T}A)^{T}=A^{T}A$) og har ikke-negative egenverdier ($\lambda=\lVert A\mathbf{v}\rVert^2\ge0$ for en enhetsegenvektor). Spektralteoremet gjelder derfor uansett hvordan $A$ ser ut, og gir en ortonormal egenbasis $\mathbf{v}_1,\dots,\mathbf{v}_n$ — nettopp høyresingulærvektorene. $A^{T}A$ er $n\times n$ når $A$ er $m\times n$.

Søylene i $V$ er en ortonormal egenbasis for $A^{T}A$: $V=[\mathbf{v}_1\ \mathbf{v}_2\ \cdots\ \mathbf{v}_n]$ der $A^{T}A\,\mathbf{v}_i=\lambda_i\mathbf{v}_i$ og $\mathbf{v}_i$ er ordnet slik at $\lambda_1\ge\lambda_2\ge\dots$. Da er $V$ ortogonal ($V^{T}V=I$). Disse kalles høyresingulærvektorer fordi de står til høyre i $A=U\Sigma V^{T}$. De leses (etter normalisering) rett av vedleggets eig$(A^{T}A)$.

For hver positiv singulærverdi er venstresingulærvektoren $\mathbf{u}_i=\dfrac{1}{\sigma_i}A\mathbf{v}_i$. Disse er ortonormale, og søylene $\mathbf{u}_1,\dots,\mathbf{u}_m$ (etter utvidelse til full ortonormal basis for $\mathbb{R}^m$) danner den ortogonale matrisen $U$ ($U^{T}U=I$). De kalles venstresingulærvektorer fordi de står til venstre i $A=U\Sigma V^{T}$. Faktoren $\tfrac{1}{\sigma_i}$ er avgjørende — uten den blir $\mathbf{u}_i$ ikke en enhetsvektor.

En singulærverdidekomposisjon av en $m\times n$-matrise $A$ er en faktorisering $A=U\Sigma V^{T}$ der $U$ ($m\times m$) og $V$ ($n\times n$) er ortogonale, og $\Sigma$ ($m\times n$) har singulærverdiene $\sigma_1\ge\sigma_2\ge\dots\ge0$ på «diagonalen» og null ellers. En slik dekomposisjon finnes for enhver matrise. Den forteller at $A$ virker slik: roter/reflekter med $V^{T}$, strekk hver akse med $\sigma_i$, roter/reflekter med $U$.

Rangen til $A$ er antallet positive singulærverdier: $\operatorname{rang}A=\#\{i:\sigma_i>0\}$. Singulærverdier lik $0$ svarer til retninger som $A$ sender til null (kollapser), og teller ikke. Dette er ofte den raskeste måten å lese rangen på når SVD-en er kjent.

På enhetssfæren $\lVert\mathbf{x}\rVert=1$ er den største verdien av $\lVert A\mathbf{x}\rVert$ lik den største singulærverdien $\sigma_1$, oppnådd i $\mathbf{x}=\mathbf{v}_1$. Den minste er $\sigma_n$, i $\mathbf{x}=\mathbf{v}_n$. Dette er Rayleigh anvendt på $A^{T}A$, siden $\lVert A\mathbf{x}\rVert^2=\mathbf{x}^{T}A^{T}A\mathbf{x}$. Svaret er $\sigma_1$ (ikke $\lambda_1=\sigma_1^2$).

Beholder du bare de $k$ største leddene i summen $A=\sum_i\sigma_i\mathbf{u}_i\mathbf{v}_i^{T}$, får du den beste rang-$k$-tilnærmingen $A_k=\sum_{i=1}^{k}\sigma_i\mathbf{u}_i\mathbf{v}_i^{T}$ til $A$. Feilen styres av de forkastede singulærverdiene ($\sigma_{k+1},\dots$). Dette er ideen bak bildekomprimering og dataredusering — på pensumnivå holder det å kjenne at SVD gir denne optimale tilnærmingen.

(1) Regn $A^{T}A$. (2) Les egenverdier + ortonormale egenvektorer av vedlegget, ordne synkende → $V$. (3) $\sigma_i=\sqrt{\lambda_i}$ → $\Sigma$. (4) $\mathbf{u}_i=\tfrac{1}{\sigma_i}A\mathbf{v}_i$ for $\sigma_i>0$. (5) Utvid $\{\mathbf{u}_i\}$ til ortonormal basis → $U$. Da $A=U\Sigma V^{T}$.

For en enhetsegenvektor $\mathbf{v}$ av $A^{T}A$ er $\lambda=\mathbf{v}^{T}A^{T}A\mathbf{v}=\lVert A\mathbf{v}\rVert^2\ge0$. Derfor kan vi ta $\sigma=\sqrt{\lambda}$. $A^{T}A$ er alltid symmetrisk og positiv semidefinit.

Singulærverdiene ordnes alltid $\sigma_1\ge\sigma_2\ge\dots\ge0$. Match $V$s søyler, $\Sigma$s diagonal og $U$s søyler til samme rekkefølge — ellers stemmer ikke $A=U\Sigma V^{T}$.

Singulærverdiene er kvadratrøttene av egenverdiene til $A^{T}A$, ikke egenverdiene til $A$. For symmetrisk $A$ er $\sigma_i=|\lambda_i(A)|$; for usymmetrisk/ikke-kvadratisk $A$ har $A$ kanskje ingen (reelle) egenverdier i det hele tatt.

Gjelder bare for $\sigma_i>0$. Faktoren $\tfrac{1}{\sigma_i}$ normaliserer: $\lVert A\mathbf{v}_i\rVert=\sigma_i$, så $\mathbf{u}_i$ får lengde 1. Uten den blir $U$ ikke ortogonal.

For $i\ne j$ er $\mathbf{u}_i\cdot\mathbf{u}_j=\tfrac{1}{\sigma_i\sigma_j}(A\mathbf{v}_i)\cdot(A\mathbf{v}_j)=\tfrac{1}{\sigma_i\sigma_j}\mathbf{v}_i^{T}A^{T}A\mathbf{v}_j=\tfrac{\lambda_j}{\sigma_i\sigma_j}\mathbf{v}_i\cdot\mathbf{v}_j=0$. Ortonormaliteten arves fra at $\mathbf{v}_i$ er ortonormale egenvektorer.

Har $A$ rang $r<m$, gir formelen bare $r$ venstresingulærvektorer. Fyll opp med en ortonormal basis for komplementet (Gram–Schmidt, eller et vektorprodukt i $\mathbb{R}^3$). De ekstra søylene ganges med $0$ i $\Sigma$ og endrer ikke $A$, men gjør $U$ ortogonal.

En $m\times n$-matrise har $\min(m,n)$ singulærverdier (noen kan være $0$). $\Sigma$ er $m\times n$ med disse på diagonalen. Antallet positive er rangen.

På enhetssfæren er største strekking $\sigma_1$ (i $\mathbf{v}_1$), minste er $\sigma_n$ (i $\mathbf{v}_n$). Følger av Rayleigh på $A^{T}A$: $\lVert A\mathbf{x}\rVert^2=\mathbf{x}^{T}A^{T}A\mathbf{x}$.

I motsetning til diagonalisering (som krever egenvektorbasis) og ortogonal diagonalisering (som krever symmetri) finnes SVD for alle $m\times n$-matriser — kvadratiske eller ikke, diagonaliserbare eller ikke. Det er styrken ved SVD.

Søylene i $V$ er en ortonormal egenbasis for $A^{T}A$, så $A^{T}A=V\,\operatorname{diag}(\sigma_i^2)\,V^{T}$. Dette er spektralteoremet (kap. 6.1) anvendt på $A^{T}A$.

Er $A$ symmetrisk og positiv definit, faller SVD og ortogonal diagonalisering sammen: $\sigma_i=\lambda_i(A)$ og $U=V=P$. Er noen $\lambda_i(A)<0$, er $\sigma_i=|\lambda_i|$ og fortegnet flyttes til $U$ (jf. oppgave 4).

På eksamen får du egenverdiene og (ofte ortonormale) egenvektorene til $A^{T}A$ av vedlegget. Din jobb: ta $\sqrt{}$ for $\sigma_i$, sortere synkende, og bygge $\mathbf{u}_i=\tfrac{1}{\sigma_i}A\mathbf{v}_i$ — ikke å diagonalisere $A^{T}A$ for hånd.