Språk i innholdet

Tema 1

SVD, matriser og tensorer

Start med én idé: En matrise er en maskin. Du sender inn en vektor $x$ , og maskinen sender ut $Ax$ . SVD endrer ikke maskinen; den åpner den og viser tre enkle handlinger på innsiden:

x\xrightarrow{\;V^\top\;}\text{finn hovedretningene} \xrightarrow{\;\Sigma\;}\text{strekk eller klem} \xrightarrow{\;U\;}Ax.

Det er hele historien i miniatyr. Resten av SVD-delen forklarer hvordan vi finner disse retningene, hvor sterke de er, og hva vi kan bruke dem til. Hvis ordene rang, verdirom, radrom, kjerne og norm er litt rustne, åpner du oppfriskningen under.

Oppfriskning fra lineær algebra: fem begreper som henger sammen

Vi bruker én matrise til å koble sammen alle begrepene:

A= \begin{pmatrix} 1&0&1\\ 0&1&1 \end{pmatrix} \in\mathbb R^{2\times3}.

Formen $2\times3$ betyr at $A$ tar inn en vektor med tre koordinater og gir ut en vektor med to koordinater:

A\colon\mathbb R^3\longrightarrow\mathbb R^2.

1. Rang — hvor mange uavhengige retninger har matrisen? Kolonnene er

c_1=\begin{pmatrix}1\\0\end{pmatrix}, \qquad c_2=\begin{pmatrix}0\\1\end{pmatrix}, \qquad c_3=\begin{pmatrix}1\\1\end{pmatrix}=c_1+c_2.

Den tredje kolonnen er altså laget av de to første. Bare to kolonner gir nye retninger, så $\operatorname{rank}(A)=2$ .

2. Verdirom eller kolonnerom — hvilke svar kan komme ut? For $x=(x_1,x_2,x_3)^\top$ er

Ax=x_1c_1+x_2c_2+x_3c_3.

Alle utvektorer er derfor lineærkombinasjoner av kolonnene. Det er grunnen til at verdirommet og kolonnerommet er samme rom:

\operatorname{range}(A)=\operatorname{col}(A) =\operatorname{span}\{c_1,c_2,c_3\}.

Her spenner $c_1$ og $c_2$ ut hele $\mathbb R^2$ , så $\operatorname{range}(A)=\mathbb R^2$ . Helt konkret, velg

x=\begin{pmatrix}2\\-1\\3\end{pmatrix}.

Da får vi

Ax=\begin{pmatrix}5\\2\end{pmatrix},

Dermed ligger vektoren

\begin{pmatrix}5\\2\end{pmatrix}

i verdirommet. Verdirom betyr altså alle mulige svar $Ax$ , ikke tallene som tilfeldigvis står i matrisen.

3. Radrom — hvilke inputretninger kan matrisen registrere? Radene er vektorer i inputrommet $\mathbb R^3$ :

\operatorname{row}(A) =\operatorname{span}\left\{ \begin{pmatrix}1&0&1\end{pmatrix}, \begin{pmatrix}0&1&1\end{pmatrix} \right\}.

Radrommet og verdirommet ligger i forskjellige rom — henholdsvis $\mathbb R^3$ og $\mathbb R^2$ — men de har alltid samme dimensjon. Den dimensjonen er rangen, her $2$ .

4. Kjerne eller nullrom — hvilke input blir fullstendig visket ut? Vi løser $Ax=0$ :

x_1+x_3=0, \qquad x_2+x_3=0.

Setter vi $x_3=t$ , får vi

x=t\begin{pmatrix}-1\\-1\\1\end{pmatrix}, \qquad \ker(A)=\operatorname{span}\left\{ \begin{pmatrix}-1\\-1\\1\end{pmatrix} \right\}.

For eksempel, når

x=\begin{pmatrix}-1\\-1\\1\end{pmatrix},

får vi $Ax=0$ . Matrisen klarer ikke å skille denne retningen fra null.

5. Norm — hvor stor er en vektor eller matrise? For en vektor måler 2-normen vanlig euklidsk lengde:

\left\|\begin{pmatrix}3\\4\\0\end{pmatrix}\right\|_2 =\sqrt{3^2+4^2+0^2}=5.

For en matrise måler Frobenius-normen størrelsen på alle elementene samlet, så $\|A\|_F=\sqrt{1^2+1^2+1^2+1^2}=2$ . Operatornormen måler i stedet den største strekkfaktoren,

\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2,

og senere ser vi at den er lik den største singulærverdien.

Koblingen du bør huske fra eksemplet er

\operatorname{rank}(A) =\dim\operatorname{range}(A) =\dim\operatorname{row}(A)=2,

mens $\dim\ker(A)=1$ .

Rang–nullitet — regnskapet som alltid må gå opp. For enhver matrise $A\in\mathbb R^{m\times n}$ gjelder

\operatorname{rank}(A)+\dim\ker(A)=n.

Her er $n$ antall inputkoordinater, altså antall kolonner i $A$ . Hver inputretning havner i én av to bunker: enten kan matrisen registrere den, og da bidrar den til rangen, eller så viskes den ut, og da bidrar den til kjernen. I eksemplet vårt er regnskapet

\underbrace{2}_{\text{registrerte retninger}} +\underbrace{1}_{\text{nullretning}} =\underbrace{3}_{\text{kolonner/inputkoordinater}}.

Dette er rang–nullitet i praksis. Husk at høyresiden er antall kolonner, ikke antall rader.

Dette skal du kunne etter temaet

forklare hvorfor en matrise deles opp i enklere faktorer
lese dimensjonene i en full, redusert og kompakt SVD
regne ut en SVD for en liten matrise
tolke $U$ , $\Sigma$ og $V^\top$ geometrisk
lese rang, verdirom, kjerne og normer fra singulærverdiene
bygge og vurdere en trunkert SVD
regne ut en pseudoinvers og tolke minste-kvadraters løsninger
lese orden, fibrer og snitt og bygge rang- $1$ -tensorer med ytre produkt
bruke vektorisering, matriseringsrekkefølgen i kurset og $k$ -modusproduktet dimensjonssikkert
skille CP/ALS fra Tucker/HOSVD/HOOI og oppgi dimensjonene til alle faktorene

Del 1 · Matrisefaktorisering og egenverdidekomponering

Hvorfor faktoriserer vi en matrise?

Motivasjon

En matrisefaktorisering skriver én matrise som et produkt av enklere matriser.

For eksempel

A=BC \qquad\text{eller mer generelt}\qquad A=D_1D_2D_3.

Poenget er ikke å skrive om $A$ bare for moro skyld.

Vi velger faktorer som gjør $A$ billigere å lagre, enklere å bruke eller lettere å forstå.

Når $A=BC$ virker på en vektor, virker faktoren lengst til høyre først:

x\longmapsto Cx\longmapsto B(Cx)=Ax.

Oppfriskning: reglene for matrisemultiplikasjon

Hvis $B\in\mathbb R^{m\times k}$ og $C\in\mathbb R^{k\times n}$ , må de indre dimensjonene være like, og

BC\in\mathbb R^{m\times n}.

Oppføring $(i,j)$ er indreproduktet av rad $i$ i $B$ og kolonne $j$ i $C$ :

(BC)_{ij}=\sum_{\ell=1}^{k}b_{i\ell}c_{\ell j}.

For eksempel

\begin{pmatrix}1&2\\0&-1\end{pmatrix} \begin{pmatrix}3\\4\end{pmatrix} =\begin{pmatrix}1\cdot3+2\cdot4\\0\cdot3-1\cdot4\end{pmatrix} =\begin{pmatrix}11\\-4\end{pmatrix}.

Med flere faktorer kontrollerer du hvert nabopar og husker at faktoren lengst til høyre virker først.

Se dette i praksis

Gjennomregnet minieksempel 1. La

A=\begin{pmatrix}2&0\\0&3\end{pmatrix}.

Å skrive $A=IA$ er riktig, men avslører ingenting. En form med tre faktorer er

A= \begin{pmatrix}1&0\\0&1\end{pmatrix} \begin{pmatrix}2&0\\0&3\end{pmatrix} \begin{pmatrix}1&0\\0&1\end{pmatrix}.

Den midterste faktoren strekker første koordinat med $2$ og andre koordinat med $3$ .

Identitetsmatrisene endrer ingenting.

Det nyttige er altså ikke bare at uttrykket er et produkt. Faktorene forteller hva operasjonen gjør.

Hurtigsjekk 1. La $D=\operatorname{diag}(4,1)$ . Skriv $D$ som tre faktorer med identitetsmatriser ytterst. Hva gjør den midterste faktoren med $(x_1,x_2)^\top$ ?

Løsning

Steg 1:

D=I_2\begin{pmatrix}4&0\\0&1\end{pmatrix}I_2.

Steg 2: Identiteten til høyre lar inputen være uendret, den midterste matrisen sender $(x_1,x_2)^\top$ til $(4x_1,x_2)^\top$ , og identiteten til venstre endrer igjen ingenting. Første koordinat strekkes altså med $4$ , mens den andre er uendret.

Lavrang-idé for lagring

Før du sovner, la meg forklare dette kjapt. Lav rang betyr at en stor matrise kan bygges opp fra noen få viktige retninger, så vi lagrer disse retningene i stedet for hver eneste oppføring.

Anta at $A\in\mathbb R^{n\times n}$ er enorm. Hvis den kan representeres nøyaktig eller omtrent som

A\approx BC, \qquad B\in\mathbb R^{n\times k}, \qquad C\in\mathbb R^{k\times n}, \qquad k\ll n,

er $B$ høy og $C$ bred.

Produktet $BC$ har fortsatt størrelse $n\times n$ .

En full matrise lagrer $n^2$ tall, mens faktorene lagrer

nk+kn=2nk

tall.

Direkte bruk av $A$ krever omtrent $n^2$ operasjoner.

Faktorformen $B(Cx)$ krever omtrent $2nk$ .

Se dette i praksis

Gjennomregnet minieksempel 2. La $n=1000$ og $k=5$ . En full $1000\times1000$ -matrise lagrer

1000^2=1\,000\,000

tall. Faktorene $B\in\mathbb R^{1000\times5}$ og $C\in\mathbb R^{5\times1000}$ lagrer

1000\cdot5+5\cdot1000=10\,000

tall. Faktorformen bruker derfor $1/100$ så mange tall—en komprimering med faktor $100$ .

Hurtigsjekk 2. En $2400\times2400$ -matrise tilnærmes med $BC$ med indre dimensjon $k=12$ . Finn dimensjonene til $B,C$ , sammenlign $n^2$ med $2nk$ , og oppgi komprimeringsfaktoren.

Løsning

Steg 1: $B$ må være $2400\times12$ , og $C$ må være $12\times2400$ .

Steg 2: Den fulle matrisen lagrer

2400^2=5\,760\,000

tall, mens faktorene lagrer

2\cdot2400\cdot12=57\,600.

Steg 3: Siden $5\,760\,000/57\,600=100$ , bruker faktorformen $1/100$ så mange tall—en komprimering med faktor $100$ .

Egenverdidekomponering som utgangspunkt

Påminnelse: egenverdier og egenvektorer

En egenverdi $\lambda$ til en kvadratisk matrise $A$ og en tilhørende egenvektor $v\ne0$ oppfyller

Av=\lambda v.

Slik finner vi egenparene:

Løs den karakteristiske ligningen $\det(A-\lambda I)=0$ .
For hver egenverdi $\lambda_i$ , løs $(A-\lambda_iI)v_i=0$ .
Normaliser egenvektorene når vi trenger en ortonormal basis.

Se dette i praksis

Gjennomregnet minieksempel 3. For

A=\begin{pmatrix}2&0\\0&5\end{pmatrix}

har vi

A\begin{pmatrix}1\\0\end{pmatrix} =2\begin{pmatrix}1\\0\end{pmatrix}, \qquad A\begin{pmatrix}0\\1\end{pmatrix} =5\begin{pmatrix}0\\1\end{pmatrix}.

Koordinataksene er altså egenvektorretninger med egenverdier $2$ og $5$ .

Hurtigsjekk 3. Finn egenparene til $D=\operatorname{diag}(4,-2)$ , og forklar den negative egenverdien geometrisk.

Løsning

Steg 1: $De_1=4e_1$ , så $(4,e_1)$ er ett egenpar.

Steg 2: $De_2=-2e_2$ , så $(-2,e_2)$ er det andre egenparet.

Steg 3: Tallet $-2$ betyr at $e_2$ -retningen strekkes med $2$ og snus.

Eksempel: diagonaliserbar matrise

Eksemplet fra forelesningsnotatene er

A=\frac14\begin{pmatrix}5&-3\\-3&5\end{pmatrix}.

Enhetsegenvektorene og egenverdiene er

v_1=\frac1{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix}, \quad \lambda_1=2, \qquad v_2=\frac1{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}, \quad \lambda_2=\frac12.

Dermed er

A=V\Lambda V^\top, \qquad V=(v_1\ v_2), \qquad \Lambda=\operatorname{diag}\left(2,\frac12\right).

Rekkefølgen betyr noe: Hver diagonalverdi i $\Lambda$ må stå ved kolonnen i $V$ som tilhører samme egenpar.

Geometrisk betydning

Fordi dette eksemplet er symmetrisk, gir de ortonormale egenvektorene hovedaksene til bildet av enhetssirkelen. $v_1$ -retningen strekkes med $2$ , mens $v_2$ -retningen forkortes med $1/2$ .

Se dette i praksis

Gjennomregnet minieksempel 4. For

D=\begin{pmatrix}3&0\\0&1\end{pmatrix}

blir enhetsvektorene $e_1$ og $e_2$ sendt til $3e_1$ og $e_2$ . Enhetssirkelen blir derfor en ellipse med vannrett halvakse $3$ og loddrett halvakse $1$ .

Hurtigsjekk 4. Beskriv bildet av enhetssirkelen under $D=\operatorname{diag}(4,2)$ . Hva er hovedretningene og halvaksenes lengder?

Løsning

Steg 1: $De_1=4e_1$ og $De_2=2e_2$ .

Steg 2: Hovedretningene er dermed koordinataksene.

Steg 3: Bildet er en ellipse med halvakser $4$ og $2$ .

Appendiks: egenverdiberegning og to snarveier i nullrommet

For forelesningsmatrisen er

\det(A-\lambda I) =\left(\frac54-\lambda\right)^2-\frac9{16} =\lambda^2-\frac52\lambda+1.

Røttene er $\lambda=1/2$ og $\lambda=2$ .

Mønstersnarvei 1: motsatte kolonner. Hvis kolonnene i $A-\lambda I$ er $c_1$ og $c_2=-c_1$ , er

(A-\lambda I)\begin{pmatrix}1\\1\end{pmatrix}=c_1+c_2=0.

For $\lambda=1/2$ her er

A-\frac12I=\begin{pmatrix}3/4&-3/4\\-3/4&3/4\end{pmatrix},

så

\begin{pmatrix}1\\1\end{pmatrix}

ligger synlig i nullrommet.

Mønstersnarvei 2: identiske kolonner. Hvis $c_1=c_2$ , er

(A-\lambda I)\begin{pmatrix}1\\-1\end{pmatrix}=c_1-c_2=0.

For $\lambda=2$ her er

A-2I=\begin{pmatrix}-3/4&-3/4\\-3/4&-3/4\end{pmatrix},

så

\begin{pmatrix}1\\-1\end{pmatrix}

ligger i nullrommet.

Dette er raske observasjoner av nullrommet, ikke universelle regler for egenvektorer.

Hvis kolonnemønsteret mangler, må ligningene løses på vanlig måte.

For en $2\times2$ -matrise der alle elementene er like,

J=a\begin{pmatrix}1&1\\1&1\end{pmatrix},

summerer hver rad til $2a$ , så

J\begin{pmatrix}1\\1\end{pmatrix} =2a\begin{pmatrix}1\\1\end{pmatrix}.

Alle vektorer med koordinatsum null blir visket ut.

Spesielt er

J\begin{pmatrix}1\\-1\end{pmatrix}=0.

Egenparene er derfor radsum-paret

\left(2a,\begin{pmatrix}1\\1\end{pmatrix}\right)

og nullsum-paret

\left(0,\begin{pmatrix}1\\-1\end{pmatrix}\right).

Hvorfor egenverdier ikke er nok

Begrensninger ved egenverdidekomponering

Det reelle geometriske egenverdibildet fungerer ryddig bare når $A$ har en nyttig reell egenbasis.

Tre problemer dukker opp:

Rektangulære matriser har ingen vanlig egenverdidekomponering.
Defekte matriser har for få egenvektorer.
Reelle rotasjoner kan ha bare komplekse egenverdier.

Se dette i praksis

Gjennomregnet minieksempel 5. Matrisen

R=\begin{pmatrix}0&-1\\1&0\end{pmatrix}

roterer alle vektorer $90^\circ$ . Spesielt er $Re_1=e_2$ , som ikke er parallell med $e_1$ . Det karakteristiske polynomet er $\lambda^2+1$ , så det finnes ingen reelle egenverdier eller reelle egenvektorretninger. SVD gir likevel reelle, ikke-negative singulærverdier.

Hurtigsjekk 5. La $S=\begin{pmatrix}0&1\\-1&0\end{pmatrix}$ . Vis at den roterer $-90^\circ$ og ikke har reelle egenverdier.

Løsning

Steg 1:

Se_1=\begin{pmatrix}0\\-1\end{pmatrix}=-e_2,

så den positive vannrette retningen roteres $90^\circ$ med klokken.

Steg 2:

\det(S-\lambda I) =\det\begin{pmatrix}-\lambda&1\\-1&-\lambda\end{pmatrix} =\lambda^2+1.

Steg 3: Røttene er $\pm i$ , så det finnes ingen reelle egenverdier.

Eksempel: ikke-diagonaliserbar matrise

For

A=\begin{pmatrix}1&c\\0&1\end{pmatrix}, \qquad c\ne0,

er den eneste egenverdien $1$ , med algebraisk multiplisitet $2$ . Men

(A-I)v=0 \quad\Longrightarrow\quad cv_2=0,

så hver egenvektor er et multiplum av

\begin{pmatrix}1\\0\end{pmatrix}.

Den geometriske multiplisiteten er bare $1$ .

Derfor kan $A$ ikke diagonaliseres. Det er nettopp for slike matriser at SVD er mer robust.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 2 · Singulærverdidekomponering

Ortogonale matriser

En kvadratisk matrise $Q=(q_1\ \cdots\ q_n)$ er ortogonal når

Q^\top Q=I.

Dette er ekvivalent med at kolonnene er ortonormale:

q_i^\top q_j=\begin{cases}1,&i=j,\\0,&i\ne j.\end{cases}

Ekvivalensen kan leses oppføring for oppføring. Hvis en rektangulær SVD-faktor skrives $U_r=(u_1\ \cdots\ u_r)$ , er

(U_r^\top U_r)_{ij}=u_i^\top u_j=\delta_{ij}.

Likheten $U_r^\top U_r=I_r$ sier at kolonnene har norm $1$ og står vinkelrett på hverandre.

Ikke snu utsagnet blindt.

$U_rU_r^\top$ er bare identitetsmatrisen når $U_r$ er kvadratisk og ortogonal.

Kontroller ortonormale kolonner på forelesningsmatrisen på 3 ganger 2

For matrisen som brukes igjen i transponeringseksemplet,

A_2=\begin{pmatrix}2&1\\1&2\\1&-1\end{pmatrix},

er de reduserte venstre singulærvektorene

u_1=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\end{pmatrix}, \qquad u_2=\frac1{\sqrt6}\begin{pmatrix}1\\-1\\2\end{pmatrix}.

Lengdekvadratene er

\|u_1\|_2^2=\frac{1+1}{2}=1, \qquad \|u_2\|_2^2=\frac{1+1+4}{6}=1,

og indreproduktet er

u_1^\top u_2 =\frac1{\sqrt{12}}-\frac1{\sqrt{12}}+0 =0.

Dermed har $U_r=(u_1\ u_2)$ egenskapen $U_r^\top U_r=I_2$ . Den er fortsatt en $3\times2$ -matrise, ikke en ortogonal matrise i kvadratisk forstand, og

U_rU_r^\top=P_{\operatorname{range}(A_2)}\ne I_3.

Den reduserte faktoren er nok for eksakt rekonstruksjon og pseudoinversen. Fullfør den med en tredje ortonormal vektor bare når du trenger en basis for hele $\mathbb R^3$ eller for $\ker(A_2^\top)$ .

Se dette i praksis

Gjennomregnet minieksempel 6. La

Q=\begin{pmatrix}0&-1\\1&0\end{pmatrix}.

Kolonnene er

q_1=\begin{pmatrix}0\\1\end{pmatrix}, \qquad q_2=\begin{pmatrix}-1\\0\end{pmatrix}.

Begge har lengde $1$ , og $q_1^\top q_2=0$ .

Dermed er $Q^\top Q=I$ .

For

x=\begin{pmatrix}3\\4\end{pmatrix}

får vi

Qx=\begin{pmatrix}-4\\3\end{pmatrix}.

Både $x$ og $Qx$ har lengde $5$ . Rotasjonen bevarer altså lengde.

Hurtigsjekk 6. Kontroller at $Q=\frac15\begin{pmatrix}3&-4\\4&3\end{pmatrix}$ er ortogonal, og vis direkte at den bevarer normen til

x=\begin{pmatrix}5\\0\end{pmatrix}.

Løsning

Steg 1: Hver kolonne har lengdekvadrat $(3^2+4^2)/25=1$ , og indreproduktet mellom dem er $(3(-4)+4(3))/25=0$ .

Steg 2: Derfor er $Q^\top Q=I$ .

Steg 3:

Qx=\begin{pmatrix}3\\4\end{pmatrix}, \qquad \|Qx\|_2=5=\|x\|_2.

SVD-setningen

Les produktet fra høyre mot venstre:

$V^\top$ uttrykker inputen i ortonormale inputretninger.
$\Sigma$ strekker eller kollapser koordinatene.
$U$ plasserer resultatet i ortonormale outputretninger.

Se dette i praksis

Gjennomregnet minieksempel 7. Den positive diagonalmatrisen

A=\begin{pmatrix}3&0\\0&1\end{pmatrix}

viser allerede SVD-en sin:

U=I, \qquad \Sigma=\operatorname{diag}(3,1), \qquad V=I.

Dermed er $\sigma_1=3$ og $\sigma_2=1$ .

Hurtigsjekk 7. Oppgi en SVD av $D=\operatorname{diag}(4,2)$ og finn singulærverdiene.

Løsning

Fasit:

D=I\begin{pmatrix}4&0\\0&2\end{pmatrix}I^\top.

Dermed er $\sigma_1=4$ og $\sigma_2=2$ .

Forklaring: Diagonalverdiene er allerede ikke-negative og sortert avtakende, så vi trenger ingen retningsendring.

Formen til $\Sigma$

$\Sigma$ har alltid samme form som $A$ .

Hvis $m\le n$ , har den høyst $m$ ikke-null diagonalverdier og ekstra nullkolonner.

Hvis $m\ge n$ , har den høyst $n$ ikke-null diagonalverdier og ekstra nullrader.

Se dette i praksis

Gjennomregnet minieksempel 8. Hvis $A\in\mathbb R^{3\times2}$ , er

\Sigma=\begin{pmatrix}\sigma_1&0\\0&\sigma_2\\0&0\end{pmatrix}.

Hvis $A\in\mathbb R^{2\times3}$ i stedet, er

\Sigma=\begin{pmatrix}\sigma_1&0&0\\0&\sigma_2&0\end{pmatrix}.

Hurtigsjekk 8. Skriv den generelle formen til $\Sigma$ for $A\in\mathbb R^{4\times2}$ og for $B\in\mathbb R^{2\times5}$ .

Løsning

Fasit: For $A$ er

\Sigma_A=\begin{pmatrix}\sigma_1&0\\0&\sigma_2\\0&0\\0&0\end{pmatrix}.

For $B$ er

\Sigma_B=\begin{pmatrix}\tau_1&0&0&0&0\\0&\tau_2&0&0&0\end{pmatrix}.

Begge har nøyaktig samme dimensjoner som den opprinnelige matrisen.

Forklaring: I full SVD har $\Sigma$ alltid samme rektangulære form som den opprinnelige matrisen. Bare diagonalposisjonene kan være ulike null.

Bevisidé: hvorfor finnes SVD?

For $A\ne0$ velger vi en enhetsvektor $v_1$ der $\|Av\|_2$ er størst, og setter

\sigma_1=\|Av_1\|_2, \qquad u_1=\frac{Av_1}{\sigma_1}.

Fullfør $v_1$ og $u_1$ til ortonormale basiser.

I disse basisene skiller maksimaliteten det første strekket fra en mindre restblokk.

Gjenta på restblokken. Slik bygges alle singulærretningene.

Dette er et eksistensargument, ikke eksamensmetoden. I beregninger bruker vi $A^\top A$ eller $AA^\top$ .

Hvis $A=0$ , velger vi $\Sigma=0$ og vilkårlige ortogonale $U$ og $V$ ; da er $A=U\Sigma V^\top$ med én gang.

Se dette i praksis

Gjennomregnet minieksempel 9. For $A=\operatorname{diag}(3,1)$ oppnås maksimum av $\|Ax\|_2$ over enhetsvektorene ved $v_1=e_1$ , fordi $Av_1=3e_1$ . Dermed er $\sigma_1=3$ og $u_1=e_1$ . I den gjenværende vinkelrette retningen $e_2$ er strekket $1$ , så $\sigma_2=1$ .

Hurtigsjekk 9. Bruk den samme største-strekk-ideen på $D=\operatorname{diag}(5,2)$ . Finn $v_1,u_1,\sigma_1$ og den gjenværende singulærtrippelen.

Løsning

Fasit: $v_1=u_1=e_1$ , $\sigma_1=5$ , og den gjenværende trippelen er $v_2=u_2=e_2$ , $\sigma_2=2$ .

Forklaring: $De_1=5e_1$ er det største strekket. I den vinkelrette retningen er $De_2=2e_2$ .

Full, redusert/økonomi og kompakt SVD

Jeg vet at dette ser helt jævlig ut, men la meg bryte det ned. Dette er ikke tre ulike dekomponeringer; det er de samme singulærretningene med ulik mengde bokføring av nullretninger.

La $A\in\mathbb R^{m\times n}$ og $q=\min(m,n)$ . Tre nært beslektede konvensjoner er vanlige:

Full SVD:
$A=U\Sigma V^\top, \qquad U:m\times m, \quad \Sigma:m\times n, \quad V:n\times n.$
Begge ytterfaktorene er kvadratiske ortogonale matriser:
$U^\top U=UU^\top=I_m, \qquad V^\top V=VV^\top=I_n.$

Redusert, tynn eller økonomi-SVD:

A=U_q\Sigma_qV_q^\top, \qquad U_q:m\times q, \quad \Sigma_q:q\times q, \quad V_q:n\times q.

Denne bygger fortsatt opp $A$ nøyaktig, også når noen av de $q$ singulærverdiene er null.

Kolonnene er ortonormale:

U_q^\top U_q=V_q^\top V_q=I_q.

En rektangulær $U_q$ eller $V_q$ er ikke en ortogonal matrise i den kvadratiske, fulle betydningen. Produktene i motsatt rekkefølge trenger ikke å være identitetsmatriser.

Det er nyttig å skrive økonomidimensjonene separat for høye og brede matriser:

Form på $A$	Økonomifaktorisering	Faktordimensjoner
Høy, $m\ge n$ og $q=n$	$A=U_q\Sigma_qV^\top$	$U_q:m\times n$ , $\Sigma_q:n\times n$ , $V:n\times n$
Bred, $n\ge m$ og $q=m$	$A=U\Sigma_qV_q^\top$	$U:m\times m$ , $\Sigma_q:m\times m$ , $V_q:n\times m$

I det høye tilfellet er høyrefaktoren allerede kvadratisk; i det brede tilfellet er venstrefaktoren allerede kvadratisk. Dette er den dimensjonssikre økonomikonvensjonen.

Kompakt eller rang- $r$ -SVD: Hvis $r=\operatorname{rank}(A)$ er antallet positive singulærverdier, med $r=0$ for nullmatrisen, forkaster vi alle null-singulærretningene:
$A=U_r\Sigma_rV_r^\top, \qquad U_r:m\times r, \quad \Sigma_r:r\times r, \quad V_r:n\times r.$
Her er
$U_rU_r^\top=P_{\operatorname{range}(A)}, \qquad V_rV_r^\top=P_{\ker(A)^\perp}.$
Disse projektoridentitetene gjelder de kompakte faktorene med positive singulærverdier.

Ikke bruk dem om en økonomifaktor som er fylt ut med vilkårlige null-singulærretninger. Når $A$ har full rang, er $r=q$ , og den kompakte formen er lik økonomiformen.

Økonomiformen foretrekkes vanligvis i beregninger og lagring.

Den bygger opp $A$ nøyaktig uten ubrukte basisvektorer.

Den kompakte formen er enda mindre når $A$ er rangdefekt. Den beholder akkurat de positive singulærretningene vi trenger for rekonstruksjon, pseudoinversen, verdirommet og $\ker(A)^\perp$ .

Bruk full form når du trenger komplette ortonormale basiser for $\mathbb R^m$ og $\mathbb R^n$ . Det inkluderer alle retninger i $\ker(A^\top)$ eller $\ker(A)$ .

Slik går du mellom formene:

Finn de positive singulærtriplene. De gir kompakt SVD.
Legg til ortonormale null-singulærretninger til hver tynn faktor har $q$ kolonner. Da får du økonomi-SVD.
Fullfør begge sider til fulle ortonormale basiser, og fyll $\Sigma$ med nullrader eller nullkolonner. Da får du full SVD.

For en høy matrise legger full form hovedsakelig kolonner til $U_q$ og nullrader til $\Sigma$ .

For en bred matrise legger full form hovedsakelig kolonner til $V_q$ og nullkolonner til $\Sigma$ .

Full kontra redusert SVD på den håndregnede matrisen

Den korrigerte forelesningsmatrisen som brukes i hovedeksemplet nedenfor, er

A=\begin{pmatrix}1&3\\2&2\\3&1\end{pmatrix}\in\mathbb R^{3\times2}.

Her er $q=r=2$ , så økonomi-SVD og kompakt SVD er samme form:

U_r= \begin{pmatrix} 1/\sqrt3&-1/\sqrt2\\ 1/\sqrt3&0\\ 1/\sqrt3&1/\sqrt2 \end{pmatrix}, \quad \Sigma_r=\begin{pmatrix}\sqrt{24}&0\\0&2\end{pmatrix}, \quad V_r^\top=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.

De to kolonnene i $U_r$ er ortonormale, så $U_r^\top U_r=I_2$ . Men $U_r$ er $3\times2$ , ikke en kvadratisk ortogonal matrise, og

U_rU_r^\top= \begin{pmatrix} 5/6&1/3&-1/6\\ 1/3&1/3&1/3\\ -1/6&1/3&5/6 \end{pmatrix} =P_{\operatorname{range}(A)}\ne I_3.

For å få full SVD fullfører vi kolonnene i $U_r$ med en enhetsvektor som står vinkelrett på begge. Velg

u_3=\frac1{\sqrt6}\begin{pmatrix}1\\-2\\1\end{pmatrix}.

Den ligger i venstre nullrom fordi

A^\top u_3 =\frac1{\sqrt6} \begin{pmatrix}1&2&3\\3&2&1\end{pmatrix} \begin{pmatrix}1\\-2\\1\end{pmatrix} =\frac1{\sqrt6}\begin{pmatrix}1-4+3\\3-4+1\end{pmatrix} =0.

Dermed er

U=(u_1\ u_2\ u_3) =\begin{pmatrix} 1/\sqrt3&-1/\sqrt2&1/\sqrt6\\ 1/\sqrt3&0&-2/\sqrt6\\ 1/\sqrt3&1/\sqrt2&1/\sqrt6 \end{pmatrix}, \qquad U^\top U=UU^\top=I_3,

og den fulle rektangulære diagonalfaktoren er

\Sigma= \begin{pmatrix} \sqrt{24}&0\\ 0&2\\ 0&0 \end{pmatrix}.

$V=V_r$ er allerede en full $2\times2$ ortogonal matrise.

Den ekstra basisretningen bidrar ikke fordi den kobles til en nullrad:

U\Sigma V^\top =U_r\Sigma_rV_r^\top +\underbrace{u_3\begin{pmatrix}0&0\end{pmatrix}V^\top}_{0} =A.

Den reduserte formen bygger altså opp $A$ nøyaktig.

Den er nok for singulærverdiene, $V$ , $\Sigma_r$ og

A^\dagger=V_r\Sigma_r^{-1}U_r^\top.

Den fulle formen legger bare til $u_3$ når vi ønsker en komplett basis for $\mathbb R^3$ , en eksplisitt basis for $\ker(A^\top)$ eller den komplementære projeksjonen

u_3u_3^\top=I_3-U_rU_r^\top.

Se dette i praksis

Gjennomregnet minieksempel 10. Hvis $A\in\mathbb R^{100\times3}$ har full kolonnerang, bruker full SVD en $100\times100$ -matrise $U$ , men bare tre kolonner kan bidra. Den reduserte formen bruker

U_r:100\times3, \qquad \Sigma_r:3\times3, \qquad V_r^\top:3\times3.

Hurtigsjekk 10. Oppgi dimensjonene i redusert SVD for en fullrang $8\times3$ -matrise og en fullrang $3\times8$ -matrise.

Løsning

Fasit: For $8\times3$ er

U_r:8\times3, \quad \Sigma_r:3\times3, \quad V_r^\top:3\times3.

For $3\times8$ er

U_r:3\times3, \quad \Sigma_r:3\times3, \quad V_r^\top:3\times8.

Forklaring: Redusert/økonomi-SVD bruker $q=\min(m,n)=3$ singulærretninger i begge tilfeller. Den rektangulære faktoren står på den største siden.

Transponering og symmetriske matriser

Transponeringsegenskapen

Før vi transponerer en hel SVD, tar vi den mekaniske regelen én gang:

Oppfriskning: transponer en 2 × 2-matrise

Å transponere betyr at kolonnene blir rader. For en generell $2\times2$ -matrise er regelen

\begin{pmatrix} a&b\\ c&d \end{pmatrix}^{\!\top} = \begin{pmatrix} a&c\\ b&d \end{pmatrix}.

Diagonaloppføringene $a$ og $d$ blir stående. De to oppføringene utenfor diagonalen, $b$ og $c$ , bytter plass. For eksempel:

A= \begin{pmatrix} 1&4\\ -2&3 \end{pmatrix} \quad\Longrightarrow\quad A^\top= \begin{pmatrix} 1&-2\\ 4&3 \end{pmatrix}.

En rask kontroll er at en ny transponering skal gi originalen tilbake: $(A^\top)^\top=A$ .

Transponering av $A=U\Sigma V^\top$ gir

A^\top=V\Sigma^\top U^\top.

De venstre og høyre singulærretningene bytter roller.

Strekkstørrelsene endres ikke.

Derfor har $A$ og $A^\top$ de samme singulærverdiene, og

\|A\|_2=\|A^\top\|_2.

På én linje: Hvis full SVD er $A=U\Sigma V^\top$ , får vi full SVD av den transponerte matrisen ved å bytte venstre og høyre rolle og transponere den rektangulære midtfaktoren:

\widetilde U=V, \qquad \widetilde\Sigma=\Sigma^\top, \qquad \widetilde V=U.

For en redusert SVD gir samme snarvei

A^\top=V_r\Sigma_rU_r^\top,

fordi $\Sigma_r$ er diagonal. Spesielt er $\widetilde V_r=U_r$ .

Hele transponeringssnarveien på en konkret $3\times2$-matrise

A_2=\begin{pmatrix}2&1\\1&2\\1&-1\end{pmatrix}\in\mathbb R^{3\times2}.

Den minste Gram-matrisen er

A_2^\top A_2=\begin{pmatrix}6&3\\3&6\end{pmatrix}.

Egenverdiene er $9$ og $3$ , så singulærverdiene er $3$ og $\sqrt3$ . De tilhørende normaliserte egenvektorene gir

V=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.

Formelen $u_i=A_2v_i/\sigma_i$ gir

u_1=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\end{pmatrix}, \qquad u_2=\frac1{\sqrt6}\begin{pmatrix}1\\-1\\2\end{pmatrix}, \qquad U_r=(u_1\ u_2)\in\mathbb R^{3\times2}.

En siste enhetsvektor,

u_3=\frac1{\sqrt3}\begin{pmatrix}-1\\1\\1\end{pmatrix},

oppfyller $A_2^\top u_3=0$ . En full venstrefaktor og den fulle rektangulære diagonalfaktoren er derfor

U=(u_1\ u_2\ u_3) =\begin{pmatrix} 1/\sqrt2&1/\sqrt6&-1/\sqrt3\\ 1/\sqrt2&-1/\sqrt6&1/\sqrt3\\ 0&2/\sqrt6&1/\sqrt3 \end{pmatrix}, \qquad \Sigma=\begin{pmatrix}3&0\\0&\sqrt3\\0&0\end{pmatrix}.

Faktordimensjonene for $A_2$ er

\text{full: }(3\times3)(3\times2)(2\times2), \qquad \text{redusert: }(3\times2)(2\times2)(2\times2).

Definer nå $A_3=A_2^\top\in\mathbb R^{2\times3}$ . Uten noen ny utregning får vi

A_3=A_2^\top=V\Sigma^\top U^\top =\widetilde U\widetilde\Sigma\widetilde V^\top,

der de viste fulle faktorene er

\widetilde U=V =\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}, \qquad \widetilde\Sigma=\Sigma^\top =\begin{pmatrix}3&0&0\\0&\sqrt3&0\end{pmatrix}, \qquad \widetilde V=U.

De fulle dimensjonene for $A_3$ er altså $(2\times2)(2\times3)(3\times3)$ . I redusert form er

A_3=V\Sigma_rU_r^\top, \qquad \widetilde U_r=V:2\times2, \quad \widetilde\Sigma_r=\Sigma_r:2\times2, \quad \widetilde V_r=U_r:3\times2.

Full $U,V,\widetilde U,\widetilde V$ er kvadratiske ortogonale matriser.

Den rektangulære $U_r=\widetilde V_r$ har i stedet ortonormale kolonner:

U_r^\top U_r=I_2.

Den er ikke en kvadratisk ortogonal matrise.

Transponering bytter bare hvilke singulærvektorer som beskriver input- og outputrommet.

Til slutt har

A_2A_2^\top= \begin{pmatrix}5&4&1\\4&5&-1\\1&-1&2\end{pmatrix}

egenverdiene $9,3,0$ , mens $A_2^\top A_2$ har egenverdiene $9,3$ .

Egenverdiene som ikke er null, er de samme.

Den ekstra nullen hører til $u_3\in\ker(A_2^\top)$ . Etter transponering er dette den ekstra høyre nullromsretningen til $A_3$ .

Nettopp derfor har den fulle $3\times3$ -faktoren én kolonne mer enn den reduserte faktoren.

Se dette i praksis

Gjennomregnet minieksempel 11. For $A=\operatorname{diag}(3,1)$ er $A^\top=A$ , så begge har singulærverdier $3,1$ . For den ikke-kvadratiske radmatrisen $B=(1\ 2)$ er

B^\top=\begin{pmatrix}1\\2\end{pmatrix}, \qquad \|B\|_2=\|B^\top\|_2=\sqrt{1^2+2^2}=\sqrt5.

Hurtigsjekk 11. Finn den eneste positive singulærverdien til $C=(2\ -2)$ og til $C^\top$ .

Løsning

Fasit:

CC^\top=2^2+(-2)^2=8.

Den positive singulærverdien er derfor $\sqrt8=2\sqrt2$ . Transponering endrer den ikke.

Forklaring: En matrise med én rad har én positiv singulærverdi lik den euklidske lengden til raden, og $C$ og $C^\top$ deler denne verdien.

Sammenhengen med $A^\top A$ og $AA^\top$

Her hoper symbolene seg opp, men grepet er enkelt: Sett inn SVD-en, forkort en ortogonal faktor og les av diagonalverdiene i andre.

Start dimensjonssikkert fra den fulle SVD-en $A=U\Sigma V^\top$ , der $U:m\times m$ , $\Sigma:m\times n$ og $V:n\times n$ . Da er

A^\top A =(U\Sigma V^\top)^\top(U\Sigma V^\top) =V\Sigma^\top\underbrace{U^\top U}_{I_m}\Sigma V^\top =V(\Sigma^\top\Sigma)V^\top,

og tilsvarende

AA^\top =(U\Sigma V^\top)(U\Sigma V^\top)^\top =U\Sigma\underbrace{V^\top V}_{I_n}\Sigma^\top U^\top =U(\Sigma\Sigma^\top)U^\top.

Diagonalmatrisene $\Sigma^\top\Sigma$ og $\Sigma\Sigma^\top$ inneholder de samme positive tallene $\sigma_i^2$ .

De skiller seg bare i antallet nuller.

I kompakt form er den ikke-null diagonale blokken $\Sigma_r^2$ .

Fordi $V^\top v_i=e_i$ og $U^\top u_i=e_i$ , gir multiplikasjon av de to dekomponeringene med én faktorkolonne

A^\top Av_i=\sigma_i^2v_i, \qquad AA^\top u_i=\sigma_i^2u_i.

Kolonnene i $V$ er altså egenvektorer til $A^\top A$ .

Kolonnene i $U$ er egenvektorer til $AA^\top$ .

De positive singulærverdiene er kvadratrøttene av de positive egenverdiene. For $\sigma_i>0$ er

u_i=\frac{Av_i}{\sigma_i}, \qquad v_i=\frac{A^\top u_i}{\sigma_i}.

Begge Gram-matrisene er positivt semidefinite. For hver kompatibel vektor $x$ er nemlig

x^\top A^\top Ax=(Ax)^\top(Ax)=\|Ax\|_2^2\ge0.

Derfor er egenverdiene reelle og ikke-negative, og hver singulærverdi $\sigma_i=\sqrt{\lambda_i}$ er reell og ikke-negativ.

Sammenlign begge Gram-matrisene på forelesningsmatrisen på 3 ganger 2

For

A_2=\begin{pmatrix}2&1\\1&2\\1&-1\end{pmatrix}

er den minste Gram-matrisen

A_2^\top A_2=\begin{pmatrix}6&3\\3&6\end{pmatrix},

med egenverdier $9$ og $3$ . Den større Gram-matrisen er

A_2A_2^\top =\begin{pmatrix} 5&4&1\\ 4&5&-1\\ 1&-1&2 \end{pmatrix},

med egenverdier $9,3,0$ . Dermed er

\operatorname{spec}(A_2^\top A_2)=\{9,3\}, \qquad \operatorname{spec}(A_2A_2^\top)=\{9,3,0\}.

Den ekstra nullverdien svarer til den manglende outputretningen $u_3\in\ker(A_2^\top)$ .

Begge matrisene gir singulærverdiene $3$ og $\sqrt3$ .

Velg den minste Gram-matrisen for å spare regning. Velg $A^\top A$ når du vil finne $v_i$ direkte, og $AA^\top$ når du vil finne $u_i$ direkte.

Eksamenfelle: når begge Gram-matrisene er 2 × 2

For en $2\times2$ -matrise er både $A^\top A$ og $AA^\top$ av størrelse $2\times2$ . Det finnes derfor ingen størrelsesgevinst. Valget bestemmer bare hvilke singulærvektorer du får direkte:

A^\top A=V\Sigma^2V^\top \quad\Longrightarrow\quad \text{egenvektorene er }v_i,

AA^\top=U\Sigma^2U^\top \quad\Longrightarrow\quad \text{egenvektorene er }u_i.

Singulærverdiene blir de samme. Velg én av Gram-matrisene, og koble deretter sammen venstre og høyre side med

u_i=\frac{Av_i}{\sigma_i} \qquad\text{eller}\qquad v_i=\frac{A^\top u_i}{\sigma_i}, \qquad \sigma_i>0.

Fellen er å diagonalisere begge Gram-matrisene hver for seg. Egenvektorer kan skifte fortegn. Ved gjentatte egenverdier kan du til og med velge ulike ortonormale basiser i samme egenrom. Da kan hver liste være riktig alene uten at $u_i$ og $v_i$ er paret riktig, og rekonstruksjonen kan bli feil.

A=\begin{pmatrix}2&0\\0&-3\end{pmatrix}.

Her er

A^\top A=AA^\top=\begin{pmatrix}4&0\\0&9\end{pmatrix}.

Med avtakende rekkefølge kan vi velge

V=(e_2\ e_1) =\begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad \Sigma=\operatorname{diag}(3,2).

Hvis vi bare kopierer og setter $U=V$ , får vi

U\Sigma V^\top =\begin{pmatrix}2&0\\0&3\end{pmatrix}\ne A;

minusfortegnet har forsvunnet. Formelen reparerer paret:

u_1=\frac{Ae_2}{3}=-e_2, \qquad u_2=\frac{Ae_1}{2}=e_1.

Dermed er

U=(-e_2\ e_1) =\begin{pmatrix}0&1\\-1&0\end{pmatrix}, \qquad U\Sigma V^\top=A.

Praktisk eksamensregel. Bruk $A^\top A$ når oppgaven eller notatene ber om $V$ , og lag så hvert $u_i$ med $Av_i/\sigma_i$ . Ikke finn begge sider uavhengig.

Hvis $\sigma_i=0$ , kan du ikke dele. I en full SVD fullfører du da $U$ med en enhetsvektor som er ortogonal på de venstre singulærvektorene du allerede har; den ligger i $\ker(A^\top)$ . Det er samme idé som den ekstra $u_3$ -retningen i den fulle SVD-en av en høy matrise.

Se dette i praksis

Gjennomregnet minieksempel 12. La

A=\begin{pmatrix}3&0\\0&2\\0&0\end{pmatrix}.

Da er

A^\top A=\begin{pmatrix}9&0\\0&4\end{pmatrix}.

Egenverdiene er $9$ og $4$ , så singulærverdiene til $A$ er $3$ og $2$ .

Hurtigsjekk 12. Bruk $A^\top A$ til å finne singulærverdiene til $A=\begin{pmatrix}4&0\\0&1\\0&0\end{pmatrix}$ .

Løsning

Fasit:

A^\top A=\begin{pmatrix}16&0\\0&1\end{pmatrix}.

Dermed er $\sigma_1=4$ og $\sigma_2=1$ .

Forklaring: Gram-egenverdiene er $16$ og $1$ , og singulærverdiene er de ikke-negative kvadratrøttene.

Symmetriske matriser

Hvis $A=A^\top$ har egenverdidekomponeringen $A=Q\Lambda Q^\top$ , er

A^\top A=Q\Lambda^2Q^\top.

Singulærverdiene er derfor absoluttverdiene av egenverdiene, sortert avtakende:

\sigma_i=|\lambda_i|.

Dette finner singulærverdiene, men ikke automatisk en komplett SVD.

En negativ egenverdi betyr «strekk pluss vending». Singulærverdien beholder bare størrelsen på strekket, så en full SVD må plassere fortegnet i én vektorfaktor.

La for eksempel $S=\operatorname{diag}(\operatorname{sign}\lambda_i)$ , med fortegn $1$ valgt når $\lambda_i=0$ . Da er

A=(QS)|\Lambda|Q^\top

en SVD etter at kolonnene er sortert konsekvent.

Hvis $A$ er symmetrisk positiv definit, er alle egenverdiene positive, $S=I$ , og $\sigma_i=\lambda_i$ .

Slik kjenner du raskt igjen en symmetrisk positiv semidefinit matrise. I dette kurset sjekker du symmetri først. For en reell symmetrisk $2\times2$ -matrise

B=\begin{pmatrix}a&b\\b&d\end{pmatrix}

slipper du å løse den karakteristiske ligningen:

B\text{ er PSD} \quad\Longleftrightarrow\quad \operatorname{tr}(B)\ge0 \quad\text{og}\quad \det(B)\ge0,

B\text{ er positiv definit} \quad\Longleftrightarrow\quad \operatorname{tr}(B)>0 \quad\text{og}\quad \det(B)>0.

Grunnen er at en symmetrisk matrise har reelle egenverdier, summen deres er sporet, og produktet deres er determinanten. Et ikke-negativt produkt gjør at egenverdiene har samme fortegn eller at én er null; et ikke-negativt spor velger den ikke-negative grenen.

For større symmetriske matriser sier Sylvesters kriterium at alle ledende prinsipale minorer må være positive for positiv definithet. For positiv semidefinithet må alle prinsipale minorer—ikke bare de ledende—være ikke-negative, så egenverdier er ofte enklere.

Snarveien du bør pugge i dette kurset, er at enhver $C^\top C$ og $CC^\top$ automatisk er symmetrisk PSD fordi

x^\top C^\top Cx=\|Cx\|_2^2\ge0.

Enda bedre: Hvis $B=zz^\top$ med $z\ne0$ , er $B$ med én gang symmetrisk, PSD og av rang $1$ . Den eneste positive egenverdien og singulærverdien er $\|z\|_2^2$ , og singulærretningen er $z/\|z\|_2$ .

Se dette i praksis

Gjennomregnet minieksempel 13. Først: For $A=\operatorname{diag}(-3,2)$ er egenverdiene $-3,2$ , mens singulærverdiene er $3,2$ . SVD husker størrelsen på hvert strekk; fortegnet tas opp i $U$ eller $V$ .

Se så på den symmetriske rang- $1$ -matrisen

B=\begin{pmatrix}1&2\\2&4\end{pmatrix} =\begin{pmatrix}1\\2\end{pmatrix} \begin{pmatrix}1&2\end{pmatrix} =zz^\top, \qquad z=\begin{pmatrix}1\\2\end{pmatrix}.

Den er åpenbart symmetrisk. Dessuten er

\operatorname{tr}(B)=5>0, \qquad \det(B)=4-4=0.

Dermed er $B$ PSD, men ikke positiv definit. Determinanten er null og den andre kolonnen er dobbelt så stor som den første, så rangen er $1$ . Siden $B=zz^\top$ , er

\lambda_1=\sigma_1=\|z\|_2^2=5, \qquad q_1=\frac{z}{\|z\|_2} =\frac1{\sqrt5}\begin{pmatrix}1\\2\end{pmatrix}.

Velg den vinkelrette enhetsvektoren

q_2=\frac1{\sqrt5}\begin{pmatrix}-2\\1\end{pmatrix}, \qquad Q=(q_1\ q_2).

Fordi $B$ er PSD, er egenverdidekomponeringen allerede en SVD:

B=Q\begin{pmatrix}5&0\\0&0\end{pmatrix}Q^\top, \qquad U=V=Q.

Den kompakte rang- $1$ -SVD-en er enda kortere:

B=5q_1q_1^\top.

Kjennetegn: Symmetri pluss at én ikke-null rad eller kolonne er et multiplum av den andre, skriker «rang- $1$ PSD». Hvis du kan skrive matrisen som $zz^\top$ , hopper du over begge Gram-matrisene.

Hurtigsjekk 13.

a) Finn singulærverdiene til $D=\operatorname{diag}(-5,-1)$ og oppgi én gyldig SVD.

b) Vis at

E=\begin{pmatrix}4&-2\\-2&1\end{pmatrix}

er symmetrisk PSD av rang $1$ , og oppgi både kompakt og full SVD.

Løsning

Steg 1: løs del a. Singulærverdiene er $5$ og $1$ . Ett gyldig valg er

U=\begin{pmatrix}-1&0\\0&-1\end{pmatrix}, \quad \Sigma=\begin{pmatrix}5&0\\0&1\end{pmatrix}, \quad V=I,

fordi $U\Sigma V^\top=D$ .

Steg 2: se rang- $1$ -PSD-strukturen i del b. Skriv

E= \begin{pmatrix}2\\-1\end{pmatrix} \begin{pmatrix}2&-1\end{pmatrix} =ww^\top, \qquad w=\begin{pmatrix}2\\-1\end{pmatrix}.

Dermed er $E$ symmetrisk PSD. Kolonnene er avhengige, så rangen er $1$ . Det samme ser vi fra $\operatorname{tr}(E)=5>0$ og $\det(E)=4-4=0$ .

Steg 3: les av den kompakte SVD-en. Siden $\|w\|_2^2=5$ , er

q_1=\frac1{\sqrt5}\begin{pmatrix}2\\-1\end{pmatrix}, \qquad E=5q_1q_1^\top.

Dermed har den kompakte SVD-en $U_r=V_r=q_1$ og $\Sigma_r=(5)$ .

Steg 4: fullfør en ortonormal basis for full SVD. Velg

q_2=\frac1{\sqrt5}\begin{pmatrix}1\\2\end{pmatrix}, \qquad Q=\frac1{\sqrt5}\begin{pmatrix}2&1\\-1&2\end{pmatrix}.

Da er $q_1^\top q_2=0$ og

E=Q\begin{pmatrix}5&0\\0&0\end{pmatrix}Q^\top.

Én full SVD er derfor $U=V=Q$ og $\Sigma=\operatorname{diag}(5,0)$ .

Oppskrift for håndregning

Slik regner du ut en liten SVD analytisk:

Skriv dimensjonene.
Bygg den minste av $A^\top A$ og $AA^\top$ .
Finn de ikke-negative egenverdiene.
Ta kvadratrøttene og sorter avtakende.
Normaliser de tilhørende egenvektorene.
Bruk $u_i=Av_i/\sigma_i$ eller $v_i=A^\top u_i/\sigma_i$ .
Hold hver singulærtrippel i samme rekkefølge.
Multipliser tilbake og kontroller $A=U_r\Sigma_rV_r^\top$ .

Se dette i praksis

Gjennomregnet minieksempel 14. For

A=\begin{pmatrix}1&0\\0&2\\0&0\end{pmatrix}\in\mathbb R^{3\times2}

er $A^\top A$ bare $2\times2$ , mens $AA^\top$ er $3\times3$ . Vi velger

A^\top A=\operatorname{diag}(1,4),

så singulærverdiene er $2,1$ etter sortering.

Hurtigsjekk 14. For $A=\begin{pmatrix}2&0\\0&3\\0&0\\0&0\end{pmatrix}$ , finn den minste Gram-matrisen og singulærverdiene.

Løsning

Fasit: $A^\top A$ er den minste Gram-matrisen, og singulærverdiene er $3$ og $2$ .

Forklaring: $A$ er $4\times2$ , så $A^\top A$ er bare $2\times2$ :

A^\top A=\operatorname{diag}(4,9).

Egenverdiene er $9,4$ etter sortering. Kvadratrøttene er $3,2$ .

SVD finnes selv når diagonalisering feiler

En skjærmatrise kan ha for få lineært uavhengige egenvektorer til å kunne diagonaliseres. SVD har ikke denne begrensningen: Den bruker én ortonormal basis i inputrommet og en annen i outputrommet. Åpne utregningen nedenfor når du vil se hele algebraen.

Full utregning: SVD av en skjærmatrise som ikke kan diagonaliseres

For skjærmatrisen fra forelesningen,

A=\begin{pmatrix}1&c\\0&1\end{pmatrix}, \qquad c\ne0,

AA^\top=\begin{pmatrix}1+c^2&c\\c&1\end{pmatrix}.

Egenverdiene er

\lambda_{1,2}=1+\frac{c^2}{2}\pm\sqrt{c^2+\frac{c^4}{4}},

så singulærverdiene er kvadratrøttene. For $c=8/3$ forenkles de til $3$ og $1/3$ , og én SVD er

U=\frac1{\sqrt{10}}\begin{pmatrix}3&-1\\1&3\end{pmatrix}, \quad \Sigma=\begin{pmatrix}3&0\\0&1/3\end{pmatrix}, \quad V=\frac1{\sqrt{10}}\begin{pmatrix}1&-3\\3&1\end{pmatrix}.

Matrisen kan ikke diagonaliseres, men SVD skiller den likevel i ortogonale retningsendringer og ikke-negative strekk.

Hovedeksempel: en komplett håndregnet redusert SVD

Dette er hele håndregningsoppskriften på den korrigerte forelesningsmatrisen. De åtte stegene er foldet sammen slik at hovedsiden forblir lett å skumme; åpne dem når du vil se hver multiplikasjon og dimensjonskontroll.

Full utregning: en redusert SVD fra start til slutt

Bruk den korrigerte forelesningsmatrisen

A=\begin{pmatrix}1&3\\2&2\\3&1\end{pmatrix}.

Steg 1: les dimensjonene og velg den minste Gram-matrisen. $A$ er $3\times2$ , så de reduserte faktorene må ha dimensjoner $U_r:3\times2$ , $\Sigma_r:2\times2$ og $V_r^\top:2\times2$ . Den minste Gram-matrisen er $A^\top A$ .

Steg 2: bygg $A^\top A$ element for element. Kolonnene er

a_1=\begin{pmatrix}1\\2\\3\end{pmatrix}, \qquad a_2=\begin{pmatrix}3\\2\\1\end{pmatrix}.

Indreproduktene er

a_1^\top a_1=1+4+9=14, \qquad a_2^\top a_2=9+4+1=14,

a_1^\top a_2=3+4+3=10.

Dermed er

A^\top A=\begin{pmatrix}14&10\\10&14\end{pmatrix}.

Steg 3: finn egenverdiene.

\det(A^\top A-\lambda I) =(14-\lambda)^2-100 =\lambda^2-28\lambda+96 =(\lambda-24)(\lambda-4).

Altså er $\lambda_1=24$ og $\lambda_2=4$ .

Steg 4: ta kvadratrøtter, ikke bruk egenverdiene direkte.

\sigma_1=\sqrt{24}=2\sqrt6, \qquad \sigma_2=\sqrt4=2.

Steg 5: finn og normaliser de høyre singulærvektorene. For $\lambda_1=24$ er kolonnene i $A^\top A-24I$ motsatte. Derfor ligger

\begin{pmatrix}1\\1\end{pmatrix}

i nullrommet.

For $\lambda_2=4$ er kolonnene identiske. Derfor ligger

\begin{pmatrix}1\\-1\end{pmatrix}

i nullrommet. Etter normalisering:

v_1=\frac1{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}, \qquad v_2=\frac1{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix}.

Steg 6: finn de venstre singulærvektorene. Bruk $u_i=Av_i/\sigma_i$ :

Av_1=\frac1{\sqrt2}\begin{pmatrix}4\\4\\4\end{pmatrix} \quad\Longrightarrow\quad u_1=\frac1{\sqrt3}\begin{pmatrix}1\\1\\1\end{pmatrix},

Av_2=\frac1{\sqrt2}\begin{pmatrix}-2\\0\\2\end{pmatrix} \quad\Longrightarrow\quad u_2=\frac1{\sqrt2}\begin{pmatrix}-1\\0\\1\end{pmatrix}.

Steg 7: sett sammen tilhørende kolonner i samme rekkefølge.

U_r=\begin{pmatrix}1/\sqrt3&-1/\sqrt2\\1/\sqrt3&0\\1/\sqrt3&1/\sqrt2\end{pmatrix}, \quad \Sigma_r=\begin{pmatrix}\sqrt{24}&0\\0&2\end{pmatrix}, \quad V_r=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.

Dimensjonskontrollen er $(3\times2)(2\times2)(2\times2)=3\times2$ .

Steg 8: multipliser tilbake via rang-1-summen. Det første leddet er

\sigma_1u_1v_1^\top =\begin{pmatrix}2&2\\2&2\\2&2\end{pmatrix},

og det andre er

\sigma_2u_2v_2^\top =\begin{pmatrix}-1&1\\0&0\\1&-1\end{pmatrix}.

Summen er nøyaktig

\begin{pmatrix}2&2\\2&2\\2&2\end{pmatrix} +\begin{pmatrix}-1&1\\0&0\\1&-1\end{pmatrix} =\begin{pmatrix}1&3\\2&2\\3&1\end{pmatrix}=A.

Uavhengig Axia-kontroll. Behold også den eksisterende matrisen

\widetilde A=\begin{pmatrix}2&0\\0&2\\1&1\end{pmatrix}

for å vise at oppskriften ikke er knyttet til forelesningstallene. Her er

\widetilde A^\top\widetilde A =\begin{pmatrix}5&1\\1&5\end{pmatrix},

så egenverdiene er $6,4$ og singulærverdiene er $\sqrt6,2$ .

De høyre singulærvektorene er

\widetilde v_1=\frac1{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}, \qquad \widetilde v_2=\frac1{\sqrt2}\begin{pmatrix}1\\-1\end{pmatrix}.

De venstre singulærvektorene er

\widetilde u_1=\frac1{\sqrt3}\begin{pmatrix}1\\1\\1\end{pmatrix}, \qquad \widetilde u_2=\frac1{\sqrt2}\begin{pmatrix}1\\-1\\0\end{pmatrix}.

De to rang-1-leddene bygger matrisen nøyaktig:

\widetilde A= \begin{pmatrix}1&1\\1&1\\1&1\end{pmatrix} +\begin{pmatrix}1&-1\\-1&1\\0&0\end{pmatrix}.

Også denne multiplikasjonen gir nøyaktig den opprinnelige matrisen.

Se det før du regner

SVD er en maskin med tre steg

Ax = U(Σ(Vᵀx))

Én vanskelig transformasjon blir: rett inn retningene → strekk eller klem → plasser resultatet.

Start med en vektor x. En matrise kan endre både retningen og lengden.

Laster interaktiv modell / Loading interactive model …

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 3 · Geometri, matriseegenskaper og beste lavrang-approksimasjon

Geometrien: $V^\top$ , så $\Sigma$ , så $U$

SVD sender enhetssirkelen gjennom en ortogonal retningsendring, aksevis skalering og en siste ortogonal retningsendring. Resultatet er en ellipse med halvakser lik singulærverdiene.Full størrelse / Full size ↗

Se dette i praksis

Gjennomregnet minieksempel 15. For $A=\operatorname{diag}(2,1)$ er

Ae_1=2e_1, \qquad Ae_2=e_2.

Enhetssirkelen blir en ellipse med halvakser $2$ og $1$ . Disse lengdene er nettopp singulærverdiene.

Hurtigsjekk 15. For $A=\operatorname{diag}(3,1/2)$ , finn bildene av $e_1,e_2$ og beskriv ellipsen.

Løsning

Fasit: $Ae_1=3e_1$ og $Ae_2=(1/2)e_2$ . Ellipsen har vannrett halvakse $3$ og loddrett halvakse $1/2$ .

Forklaring: Bildene av enhetsvektorene viser halvaksenes retninger og lengder direkte.

Rang-1-summen og virkningen på en vektor

Den kompakte SVD-en kan skrives

A=\sum_{i=1}^r\sigma_i u_iv_i^\top,

der hvert $u_iv_i^\top$ er en rang-1-matrise. Når matrisen virker på $x$ , får vi

Ax=\sum_{i=1}^r\sigma_i\langle v_i,x\rangle u_i.

Formelen måler først hvor mye av $x$ som ligger i hver $v_i$ -retning og bygger deretter outputen i den tilhørende $u_i$ -retningen.

En matrise bygges som en sum av vektede rang-1-lag. De første lagene har størst vekt fordi singulærverdiene er sortert.Full størrelse / Full size ↗

Se dette i praksis

Gjennomregnet minieksempel 16. For $A=\operatorname{diag}(3,1)$ er

A=3\begin{pmatrix}1\\0\end{pmatrix}(1\ 0) +1\begin{pmatrix}0\\1\end{pmatrix}(0\ 1) =\begin{pmatrix}3&0\\0&1\end{pmatrix}.

Hurtigsjekk 16. Skriv $D=\operatorname{diag}(4,2)$ som en sum av to vektede rang-1-matriser, og bruk summen til å regne ut

D\begin{pmatrix}1\\3\end{pmatrix}.

Løsning

Fasit:

D=4e_1e_1^\top+2e_2e_2^\top.

Dermed er

D\begin{pmatrix}1\\3\end{pmatrix} =4\left\langle e_1,\begin{pmatrix}1\\3\end{pmatrix}\right\rangle e_1 +2\left\langle e_2,\begin{pmatrix}1\\3\end{pmatrix}\right\rangle e_2 =\begin{pmatrix}4\\6\end{pmatrix}.

Forklaring: De to indreproduktene leser av inputkoordinatene $1$ og $3$ . Deretter skaleres de med $4$ og $2$ .

Rang og singulærverdier lik null

La $r$ være antallet positive singulærverdier; for nullmatrisen setter vi $r=0$ . Da er

A=\sum_{i=1}^r\sigma_i u_iv_i^\top,

fordi singulærverdier lik null ikke bidrar.

Se dette i praksis

Gjennomregnet minieksempel 17. For $A=\operatorname{diag}(2,0)$ er singulærverdiene $2,0$ . Bare én er positiv, så $r=1$ og $\operatorname{rank}(A)=1$ . Den andre inputretningen kollapser til null.

Hurtigsjekk 17. Finn rangen til $D=\operatorname{diag}(5,0,0)$ , og identifiser den aktive og de kollapsede koordinatretningene.

Løsning

Fasit: $\operatorname{rank}(D)=1$ . $e_1$ er aktiv, mens $e_2$ og $e_3$ kollapser.

Forklaring: Bare $\sigma_1=5$ er positiv. Null-singulærverdiene bidrar ingen aktive retninger.

Hva SVD avslører uten at vi bygger opp $A$

De positive singulærtriplene gir

\operatorname{rank}(A)=r, \qquad \operatorname{range}(A)=\operatorname{span}\{u_1,\ldots,u_r\},

\ker(A)=\operatorname{span}\{v_1,\ldots,v_r\}^{\perp}, \qquad \|A\|_2=\sigma_1,

\|A\|_F=\left(\sum_{i=1}^r\sigma_i^2\right)^{1/2}.

Du trenger ikke bygge opp $A$ på nytt for å lese disse egenskapene. De ligger allerede i singulærverdiene og singulærvektorene.

Se dette i praksis

Gjennomregnet minieksempel 18. For $A=\operatorname{diag}(4,0)$ er $r=1$ , $\|A\|_2=4$ , $\|A\|_F=4$ , og

\operatorname{range}(A)=\operatorname{span}\{e_1\}, \qquad \ker(A)=\operatorname{span}\{e_2\}.

Hurtigsjekk 18. For $A=\begin{pmatrix}3&0&0\\0&2&0\end{pmatrix}$ , finn rang, verdirom, kjerne, spektralnorm og Frobenius-norm.

Løsning

Fasit: Rangen er $2$ , verdirommet er $\mathbb R^2$ , og $\ker(A)=\operatorname{span}\{e_3\}$ . Dessuten er

\|A\|_2=3, \qquad \|A\|_F=\sqrt{3^2+2^2}=\sqrt{13}.

Forklaring: De positive singulærverdiene er $3,2$ . Den tredje inputkoordinaten har singulærverdi null og kollapser.

Trunkert SVD

For $0\le k\le r$ definerer vi

A_k=\sum_{i=1}^k\sigma_i u_iv_i^\top.

$A_k$ beholder de $k$ sterkeste singulærretningene og har rang høyst $k$ .

Eckart–Young-teoremet

For $0\le k<r$ løser $A_k$ begge problemene

\min_{\operatorname{rank}(B)\le k}\|A-B\|_2 \quad\text{og}\quad \min_{\operatorname{rank}(B)\le k}\|A-B\|_F.

De optimale feilene er

\|A-A_k\|_2=\sigma_{k+1}, \qquad \|A-A_k\|_F=\left(\sum_{i=k+1}^r\sigma_i^2\right)^{1/2}.

For $k=r$ er $A_k=A$ , og begge feilene er null.

Et fallende singulærverdispekter der de første verdiene beholdes og halen forkastes. Spektralfeilen styres av den første forkastede verdien, mens Frobenius-feilen bruker hele halen.Full størrelse / Full size ↗

Eksempel: beste rang-1-approksimasjon

Se dette i praksis

Gjennomregnet minieksempel 19. For $A=\operatorname{diag}(5,1)$ er den beste rang-1-approksimasjonen

A_1=\operatorname{diag}(5,0).

Residualen er $\operatorname{diag}(0,1)$ , så

\|A-A_1\|_2=1, \qquad \|A-A_1\|_F=1.

Hurtigsjekk 19. Finn den beste rang-1-approksimasjonen til $D=\operatorname{diag}(6,2)$ og begge feilnormene.

Løsning

Fasit: Behold den største singulærverdien $6$ :

D_1=\operatorname{diag}(6,0).

Den eneste forkastede singulærverdien er $2$ , så

\|D-D_1\|_2=\|D-D_1\|_F=2.

Forklaring: Den eneste forkastede singulærverdien er $2$ , så både den største forkastede retningen og hele haleenergien har størrelse $2$ .

Hvorfor teoremet er optimalt

Halen $A-A_k$ har selv en SVD med singulærverdier $\sigma_{k+1},\ldots,\sigma_r$ .

Det gir de to feilformlene direkte.

For å se hvorfor ingen annen rang- $k$ -matrise $B$ kan gjøre det bedre, observer at $\ker(B)$ må ha en ikke-null enhetsvektor $z$ i $\operatorname{span}\{v_1,\ldots,v_{k+1}\}$ .

Da er $Bz=0$ og

\|(A-B)z\|_2=\|Az\|_2\ge\sigma_{k+1}.

Dette nullromsargumentet beviser den nedre grensen i spektralnorm.

For Frobenius-normen roterer vi inn i singulærvektorkoordinatene og bruker Pytagoras.

En rang- $k$ -matrise kan høyst fange energien $\sum_{i=1}^k\sigma_i^2$ , så haleenergien $\sum_{i=k+1}^r\sigma_i^2$ kan ikke unngås.

Trunkeringen $A_k$ oppnår begge de nedre grensene.

For forelesningsmatrisen fra Del 2 er det beste rang-1-leddet

A_1=\sigma_1u_1v_1^\top =\begin{pmatrix}2&2\\2&2\\2&2\end{pmatrix},

og begge feilene er lik den eneste forkastede singulærverdien $\sigma_2=2$ .

Lagring av en trunkert SVD

Lagring av $A_k=U_k\Sigma_kV_k^\top$ , med singulærverdiene lagret som en liste, krever

mk+k+nk=k(m+n+1)

tall i stedet for $mn$ . Dette er nyttig bare når $k(m+n+1)\ll mn$ og de forkastede singulærverdiene er små nok.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 4 · Moore–Penrose-inversen

Fra invers til pseudoinvers

Start med den kompakte SVD-en

A=U_r\Sigma_rV_r^\top.

Her inneholder $\Sigma_r$ bare de $r$ positive singulærverdiene. Pseudoinversen er

A^\dagger=V_r\Sigma_r^{-1}U_r^\top.

Les formelen fra høyre mot venstre:

$U_r^\top$ måler hvor mye av dataene som ligger i hver mulig output-retning.
$\Sigma_r^{-1}$ angrer de positive strekkene.
$V_r$ bygger en inputvektor av resultatet.

Retninger som $A$ har knust til null, finnes ikke i $\Sigma_r^{-1}$ . Vi forsøker altså aldri å regne ut $1/0$ .

De fire vanligste eksamensvariantene er:

Situasjon	Raskeste formel	Hva svaret betyr
$A$ er kvadratisk og invertibel	$A^\dagger=A^{-1}$	én eksakt løsning
$A$ er høy og har full kolonnerang	$A^\dagger=(A^\top A)^{-1}A^\top$	entydig minste-kvadraters løsning
$A$ er bred og har full radrang	$A^\dagger=A^\top(AA^\top)^{-1}$	eksakt løsning med minst norm
$A$ har rangmangel	$A^\dagger=V_r\Sigma_r^{-1}U_r^\top$	beste tilpasning først, minst norm etterpå

Fire tilfeller, fire utregninger

Interaktiv utregningVelg matrisetilfellet

A† = A⁻¹

Rangkontrollen velger formelen. Bruk deretter steg 1–4 for å følge ett talleksempel helt frem til kontroll og tolkning.

Steg 1 av 4Kontroller rangbetingelsen

det(A) = 2 · 1 − 1 · 1 = 1 ≠ 0Dermed finnes den vanlige inversen.

Laster interaktiv modell / Loading interactive model …

Ikke velg en kortformel før du har kontrollert rangbetingelsen. SVD-formelen virker alltid.

Se dette i praksis

Gjennomregnet minieksempel 20. La

D=\operatorname{diag}(4,2,0), \qquad b=\begin{pmatrix}8\\6\\5\end{pmatrix}.

Matrisen strekker de to første retningene med $4$ og $2$ , men knuser den tredje retningen helt. Derfor finnes ikke $D^{-1}$ . Pseudoinversen snur bare strekkene som fortsatt kan snus:

D^\dagger=\operatorname{diag}(1/4,1/2,0).

Når vi bruker den på $b$ , får vi

x^\dagger=D^\dagger b =\begin{pmatrix}2\\3\\0\end{pmatrix}.

Hvorfor blir siste koordinat null? Hver vektor $Dx$ har tredje koordinat lik null, så tallet $5$ i $b$ er en output matrisen aldri kan lage. Setter vi løsningen inn igjen, får vi

DD^\dagger b =\begin{pmatrix}8\\6\\0\end{pmatrix}, \qquad b-DD^\dagger b =\begin{pmatrix}0\\0\\5\end{pmatrix}.

Pseudoinversen gjør altså to ting: Den reverserer retningene som overlevde, og fjerner output-retningen som er umulig å treffe. Derfor er

D^\dagger D=DD^\dagger=\operatorname{diag}(1,1,0),

ikke $I_3$ . Hadde den siste diagonalverdien også vært positiv, ville pseudoinversen vært den vanlige inversen, og produktet ville blitt identiteten.

Vi kan også se begge Penrose-rekonstruksjonene direkte:

DD^\dagger D=D, \qquad D^\dagger DD^\dagger=D^\dagger.

Til slutt: Alle vektorer

x=\begin{pmatrix}2\\3\\t\end{pmatrix}, \qquad t\in\mathbb R,

gir den samme best mulige outputen. Den frie tredje koordinaten ligger i kjernen til $D$ . Pseudoinversen velger $t=0$ , fordi

\|x\|_2^2=2^2+3^2+t^2=13+t^2

er minst akkurat da.

Hvorfor dette er en invers. $D^\dagger$ er en generalisert invers: Den opphever de to positive strekkene og lar den kollapsede retningen være null, der en tosidig invers er umulig.

Slik bekrefter du det. Her er

P=D^\dagger D=DD^\dagger=\operatorname{diag}(1,1,0)

symmetrisk, $PD=D$ og $PD^\dagger=D^\dagger$ . Dette er nettopp de to rekonstruksjonsbetingelsene og de to symmetribetingelsene i de fire Moore–Penrose-betingelsene.

Hurtigsjekk 20. La

D=\operatorname{diag}(5,2,0), \qquad b=\begin{pmatrix}15\\8\\7\end{pmatrix}.

a) Finn $D^\dagger$ .

b) Regn ut $x^\dagger=D^\dagger b$ .

c) Regn ut $DD^\dagger b$ , og forklar hva som skjer med tallet $7$ .

d) Beskriv alle minste-kvadraters løsninger, og forklar hvorfor $x^\dagger$ har minst norm.

e) Forklar hvorfor $D^\dagger$ teller som en generalisert invers, og bekreft det med rekonstruksjons- og symmetrikontrollene.

Løsning

Steg 1: Snu bare de positive strekkene.

D^\dagger=\operatorname{diag}(1/5,1/2,0).

Nullen skal forbli null. Vi skal ikke prøve å dele på den.

Steg 2: Bruk pseudoinversen på dataene.

x^\dagger=D^\dagger b =\begin{pmatrix}(1/5)15\\(1/2)8\\0\cdot7\end{pmatrix} =\begin{pmatrix}3\\4\\0\end{pmatrix}.

Steg 3: Send løsningen gjennom $D$ igjen.

DD^\dagger b =D\begin{pmatrix}3\\4\\0\end{pmatrix} =\begin{pmatrix}15\\8\\0\end{pmatrix}.

De to første koordinatene kan gjenskapes nøyaktig. Den siste kan aldri gjenskapes, fordi tredje rad i $D$ er null. Derfor blir residualen

b-DD^\dagger b=\begin{pmatrix}0\\0\\7\end{pmatrix}.

Det er akkurat den delen av $b$ som ligger utenfor verdirommet til $D$ .

Steg 4: Finn friheten i kjernen.

Alle vektorer

x=\begin{pmatrix}3\\4\\t\end{pmatrix}

gir samme tilpassede output, fordi den siste kolonnen i $D$ er null. Normen oppfyller

\|x\|_2^2=3^2+4^2+t^2=25+t^2.

Den blir minst for $t=0$ . Derfor er

x^\dagger=\begin{pmatrix}3\\4\\0\end{pmatrix}

den korteste av alle beste tilpasninger.

Hvorfor dette er en invers. Den reverserer faktorene $5$ og $2$ i retningene som overlever, og lar nullretningen være null.

Slik bekrefter du det. Med

P=D^\dagger D=DD^\dagger=\operatorname{diag}(1,1,0)

har vi $P^\top=P$ , $PD=D$ og $PD^\dagger=D^\dagger$ . Dermed er $DD^\dagger D=D$ , $D^\dagger DD^\dagger=D^\dagger$ , og begge projektorproduktene er symmetriske.

Høye matriser: minste kvadrater

Anta at

A\in\mathbb R^{m\times n}, \qquad m>n, \qquad \operatorname{rank}(A)=n.

Matrisen har flere rader enn kolonner og full kolonnerang. Hvis

A=U\Sigma V^\top

er den reduserte SVD-en, er $\Sigma\in\mathbb R^{n\times n}$ invertibel. Da kan vi skrive

A^\dagger=V\Sigma^{-1}U^\top \in\mathbb R^{n\times m}.

Her bytter formen retning: $A$ er $m\times n$ , mens $A^\dagger$ er $n\times m$ .

Produktene i de to rekkefølgene gjør forskjellige jobber:

A^\dagger A=I_n, \qquad AA^\dagger=UU^\top=P_{\operatorname{range}(A)}.

Når $Ax=b$ har flere ligninger enn ukjente, kan kravene motsi hverandre. Minste kvadrater betyr da

x^\dagger =\underset{x\in\mathbb R^n}{\operatorname{argmin}} \|Ax-b\|_2.

Hvis $A$ har full kolonnerang, er denne løsningen entydig og

x^\dagger=A^\dagger b.

Se dette i praksis

Gjennomregnet minieksempel 21. Fra fire punkter til en Moore–Penrose-invers. Vi tilpasser en linje

q(t)=x_1+x_2t

til de fire datapunktene

(-1,0{,}4),\qquad (0,2{,}2),\qquad (1,3{,}4),\qquad (2,5{,}0).

Her inneholder $x=(x_1,x_2)^\top$ konstantleddet og stigningstallet. Vektoren $x$ inneholder ikke inputverdiene $t_i$ . Ett datapunkt blir én rad. For eksempel er

q(1)=x_1+x_2\approx3{,}4 \quad\Longleftrightarrow\quad \begin{pmatrix}1&1\end{pmatrix} \begin{pmatrix}x_1\\x_2\end{pmatrix} \approx3{,}4.

Når vi stabler de fire radene, får vi

A= \begin{pmatrix} 1&-1\\ 1&0\\ 1&1\\ 1&2 \end{pmatrix}, \qquad b= \begin{pmatrix} 0{,}4\\2{,}2\\3{,}4\\5{,}0 \end{pmatrix}, \qquad Ax\approx b.

Dimensjonene forteller allerede hva som skjer:

(4\times2)(2\times1)=(4\times1).

De to kolonnene i $A$ er ikke multipler av hverandre. Derfor har $A$ full kolonnerang, og vi kan bruke

A^\dagger=(A^\top A)^{-1}A^\top.

Steg 1: Transponer $A$ . Radene blir kolonner:

A^\top= \begin{pmatrix} 1&1&1&1\\ -1&0&1&2 \end{pmatrix} \in\mathbb R^{2\times4}.

Steg 2: Dann $A^\top A$ . En $2\times4$ -matrise ganger en $4\times2$ -matrise gir en $2\times2$ -matrise:

A^\top A =\begin{pmatrix} 1+1+1+1&-1+0+1+2\\ -1+0+1+2&(-1)^2+0^2+1^2+2^2 \end{pmatrix} =\begin{pmatrix}4&2\\2&6\end{pmatrix}.

Resultatet er symmetrisk, slik enhver Gram-matrise $A^\top A$ skal være.

Steg 3: Inverter $2\times2$ -matrisen. Determinanten er

4\cdot6-2\cdot2=20.

Bytt plass på diagonalelementene, skift fortegn på elementene utenfor diagonalen, og del på determinanten:

(A^\top A)^{-1} =\frac1{20}\begin{pmatrix}6&-2\\-2&4\end{pmatrix}.

Steg 4: Multipliser med $A^\top$ . Sluttformen er $2\times4$ , altså den omvendte formen av $A$ :

A^\dagger =(A^\top A)^{-1}A^\top =\frac1{20} \begin{pmatrix}6&-2\\-2&4\end{pmatrix} \begin{pmatrix}1&1&1&1\\-1&0&1&2\end{pmatrix} =\frac1{10} \begin{pmatrix} 4&3&2&1\\ -3&-1&1&3 \end{pmatrix}.

For en høy matrise med full kolonnerang er den raskeste kontrollen

A^\dagger A=I_2.

Her blir multiplikasjonen

A^\dagger A =\frac1{10} \begin{pmatrix}4&3&2&1\\-3&-1&1&3\end{pmatrix} \begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix} =\frac1{10} \begin{pmatrix}10&0\\0&10\end{pmatrix} =I_2.

Du skal ikke forvente at $AA^\dagger=I_4$ . Dette produktet er den symmetriske projeksjonen

AA^\dagger =\frac1{10} \begin{pmatrix} 7&4&1&-2\\ 4&3&2&1\\ 1&2&3&4\\ -2&1&4&7 \end{pmatrix}.

Den projiserer en datavektor på det todimensjonale kolonnerommet til $A$ . Symmetrien, sammen med $A^\dagger A=I_2$ , gir også en kort kontroll av de fire Moore–Penrose-betingelsene.

Hvorfor dette er en invers. Siden $A$ har full kolonnerang, er $A^\dagger$ en venstreinvers: $A^\dagger A=I_2$ . Den gjenfinner enhver koeffisientvektor eksakt, selv om en tosidig invers ikke kan finnes for en $4\times2$ -matrise.

Slik bekrefter du det. Multiplikasjonen over gir numerisk $A^\dagger A=I_2$ . Produktet i motsatt rekkefølge, $AA^\dagger$ , er symmetrisk og en projeksjon. Derfor er $AA^\dagger A=A$ og $A^\dagger AA^\dagger=A^\dagger$ , slik Moore–Penrose-betingelsene krever.

Hurtigsjekk 21. La

B=\begin{pmatrix} 1&0\\ 0&1\\ 1&1 \end{pmatrix}.

Finn $B^\dagger$ med $(B^\top B)^{-1}B^\top$ , oppgi dimensjonen, og kontroller $B^\dagger B=I_2$ . Forklar hvorfor dette gjør $B^\dagger$ til en invers i det høye tilfellet, og bekreft at $BB^\dagger$ er en symmetrisk projeksjon.

Løsning

Steg 1: Bygg og inverter Gram-matrisen.

B^\top B =\begin{pmatrix}2&1\\1&2\end{pmatrix}, \qquad (B^\top B)^{-1} =\frac13\begin{pmatrix}2&-1\\-1&2\end{pmatrix}.

Steg 2: Multipliser med $B^\top$ .

B^\dagger =\frac13\begin{pmatrix} 2&-1&1\\ -1&2&1 \end{pmatrix} \in\mathbb R^{2\times3}.

Steg 3: Kontroller riktig identitet.

B^\dagger B =\frac13\begin{pmatrix}3&0\\0&3\end{pmatrix} =I_2.

Hvorfor dette er en invers. Identiteten $B^\dagger B=I_2$ sier at $B^\dagger$ opphever $B$ på enhver inputvektor. Derfor er den en venstreinvers.

Slik bekrefter du det. I motsatt rekkefølge får vi

BB^\dagger =\frac13\begin{pmatrix} 2&-1&1\\ -1&2&1\\ 1&1&2 \end{pmatrix},

som er symmetrisk. Sammen med $B^\dagger B=I_2$ gir dette $BB^\dagger B=B$ , $B^\dagger BB^\dagger=B^\dagger$ og begge symmetribetingelsene.

Se dette i praksis

Gjennomregnet minieksempel 22. Bruk pseudoinversen til å finne linjen. Vi fortsetter med matrisen, dataene og pseudoinversen fra minieksempel 21.

Minste-kvadraters-koeffisientene er

x^\dagger =A^\dagger b =\frac1{10} \begin{pmatrix}4&3&2&1\\-3&-1&1&3\end{pmatrix} \begin{pmatrix}0{,}4\\2{,}2\\3{,}4\\5{,}0\end{pmatrix} =\begin{pmatrix}2\\1{,}5\end{pmatrix}.

Les de to radene hver for seg. Første rad regner ut konstantleddet,

x_1 =\frac1{10}\bigl(4(0{,}4)+3(2{,}2)+2(3{,}4)+1(5{,}0)\bigr) =\frac{20}{10}=2,

og andre rad regner ut stigningstallet,

x_2 =\frac1{10}\bigl(-3(0{,}4)-1(2{,}2)+1(3{,}4)+3(5{,}0)\bigr) =\frac{15}{10}=1{,}5.

Vi oversetter vektoren tilbake til et polynom:

\boxed{q(t)=2+1{,}5t}.

De fire prediksjonene blir

q(-1)=2-1{,}5=0{,}5, \quad q(0)=2{,}0, \quad q(1)=2+1{,}5=3{,}5, \quad q(2)=2+2(1{,}5)=5{,}0.

Dermed er de tilpassede verdiene og residualen tilpasset minus observert

Ax^\dagger =\begin{pmatrix}0{,}5\\2{,}0\\3{,}5\\5{,}0\end{pmatrix}, \qquad e=Ax^\dagger-b =\begin{pmatrix}0{,}1\\-0{,}2\\0{,}1\\0\end{pmatrix}.

De fire beregningene er lettest å lese i en tabell:

$t_i$	observert $y_i$	tilpasset $q(t_i)$	$q(t_i)-y_i$
$-1$	$0{,}4$	$0{,}5$	$0{,}1$
$0$	$2{,}2$	$2{,}0$	$-0{,}2$
$1$	$3{,}4$	$3{,}5$	$0{,}1$
$2$	$5{,}0$	$5{,}0$	$0$

Kvadrer hvert residual før du summerer:

(0{,}1)^2=0{,}01, \qquad (-0{,}2)^2=0{,}04, \qquad (0{,}1)^2=0{,}01, \qquad 0^2=0.

Den kvadrerte feilen er derfor

\boxed{\|Ax^\dagger-b\|_2^2=0{,}01+0{,}04+0{,}01+0=0{,}06},

mens feilen i en oppgave på formen $\min_x\|Ax-b\|_2$ er

\boxed{ \|Ax^\dagger-b\|_2 =\sqrt{0{,}1^2+(-0{,}2)^2+0{,}1^2} =\frac{\sqrt6}{10} \approx0{,}245}.

Oppgi gjerne begge tallene. Da unngår du tvetydighet om «feil» betyr normen eller summen av kvadrerte avvik.

Til slutt kontrollerer vi optimalitetsbetingelsen:

A^\top e =\begin{pmatrix} 0{,}1-0{,}2+0{,}1+0\\ (-1)(0{,}1)+0(-0{,}2)+1(0{,}1)+2(0) \end{pmatrix} =\begin{pmatrix}0\\0\end{pmatrix}.

Residualen står dermed vinkelrett på begge kolonnene i $A$ . Ingen gjenværende endring av konstantledd eller stigningstall kan redusere den kvadrerte feilen.

Hvorfor dette er en invers. Fra minieksempel 21 har vi $A^\dagger A=I_2$ . Dermed er $A^\dagger$ en venstreinvers som gjenfinner koeffisientvektorer eksakt. For data utenfor kolonnerommet projiserer den først dataene på de mulige outputene.

Slik bekrefter du det. Kontroller både $A^\dagger A=I_2$ og den numeriske optimalitetskontrollen $A^\top e=0$ over. Den første bekrefter inversegenskapen; den andre bekrefter at $x^\dagger=A^\dagger b$ er minste-kvadratersløsningen.

Hurtigsjekk 22. Bruk

B=\begin{pmatrix}1&0\\0&1\\1&1\end{pmatrix}, \qquad c=\begin{pmatrix}1\\2\\4\end{pmatrix},

og $B^\dagger$ fra Hurtigsjekk 21. Regn ut de to radene i $x^\dagger=B^\dagger c$ hver for seg. Finn deretter hver prediksjon i $Bx^\dagger$ , hver komponent og hvert kvadrat i residualen $r=c-Bx^\dagger$ , den kvadrerte feilen $\|r\|_2^2$ og feilen $\|r\|_2$ . Forklar til slutt hvorfor $B^\dagger$ teller som en invers her, og oppgi hvordan resultatet bekreftes.

Løsning

Steg 1: Finn koeffisientene.

x^\dagger =\frac13\begin{pmatrix}2&-1&1\\-1&2&1\end{pmatrix} \begin{pmatrix}1\\2\\4\end{pmatrix} =\begin{pmatrix}4/3\\7/3\end{pmatrix}.

Rad for rad får vi

x_1=\frac{2(1)-1(2)+1(4)}3=\frac43, \qquad x_2=\frac{-1(1)+2(2)+1(4)}3=\frac73.

Steg 2: Regn ut hver prediksjon.

Radene i $B$ gir

(Bx^\dagger)_1=\frac43, \qquad (Bx^\dagger)_2=\frac73, \qquad (Bx^\dagger)_3=\frac43+\frac73=\frac{11}3.

Steg 3: Regn ut residualen og begge feilkonvensjonene.

Bx^\dagger =\begin{pmatrix}4/3\\7/3\\11/3\end{pmatrix}, \qquad r=c-Bx^\dagger =\begin{pmatrix}-1/3\\-1/3\\1/3\end{pmatrix}.

Hvert residualkvadrat vises separat:

\left(-\frac13\right)^2=\frac19, \qquad \left(-\frac13\right)^2=\frac19, \qquad \left(\frac13\right)^2=\frac19.

Dermed

\boxed{\|r\|_2^2=\frac19+\frac19+\frac19=\frac13}, \qquad \boxed{\|r\|_2=\sqrt{\frac13}=\frac1{\sqrt3}}.

Steg 4: Kontroller ortogonaliteten.

B^\top r =\begin{pmatrix}r_1+r_3\\r_2+r_3\end{pmatrix} =\begin{pmatrix}0\\0\end{pmatrix}.

Dermed er residualen vinkelrett på hele kolonnerommet.

Hvorfor dette er en invers. Hurtigsjekk 21 viste $B^\dagger B=I_2$ , så $B^\dagger$ er en venstreinvers: Den opphever $B$ eksakt på koeffisientvektorer.

Slik bekrefter du det. Bruk matrisekontrollen $B^\dagger B=I_2$ og løsningskontrollen $B^\top r=0$ . Det symmetriske produktet $BB^\dagger$ fra Hurtigsjekk 21 bekrefter at den tilpassede vektoren er den ortogonale projeksjonen av $c$ .

Bevisideen, én linje om gangen

Jeg vet at dette ser helt jævlig ut ved første øyekast, men hvert likhetstegn gjør bare én ting.

Siden $\Sigma V^\top\in\mathbb R^{n\times n}$ er invertibel, kan vi skrive inputen som

x=V\Sigma^{-1}y.

Da blir

Ax =U\Sigma V^\top V\Sigma^{-1}y =Uy.

Dermed er problemet

\min_x\|Ax-b\|_2^2

det samme som

\min_y\|Uy-b\|_2^2.

Kolonnene i $U$ er ortonormale. Derfor er punktet $Uy$ nærmest $b$ den ortogonale projeksjonen

Uy=UU^\top b.

Multipliser med $U^\top$ :

y=U^\top b.

Sett dette tilbake i uttrykket for $x$ :

x=V\Sigma^{-1}U^\top b=A^\dagger b.

Det er hele bevisideen: roter, projiser, angre strekket, roter tilbake.

Se dette i praksis

Gjennomregnet minieksempel 23. Visualiser linjen og endre polynomgraden. Den heltrukne linjen under er resultatet fra minieksempel 22. Hvert loddrette linjestykke er én komponent i $Ax^\dagger-b$ .

Fire datapunkter, den tilpassede linjen q(t)=2+1,5t og de fire loddrette residualene.Full størrelse / Full size ↗

Konstantleddet $2$ er den tilpassede verdien ved $t=0$ . Stigningstallet $1{,}5$ sier at den tilpassede verdien øker med $1{,}5$ når $t$ øker med én. Linjen bommer litt på tre punkter fordi fire dataverdier stiller fire krav til bare to koeffisienter.

Matrisen viser hvordan vi endrer modellen. Kolonnene er basisfunksjonene evaluert i datapunktene. Et andregradspolynom legger til kolonnen $t^2$ :

A_2= \begin{pmatrix} 1&-1&1\\ 1&0&0\\ 1&1&1\\ 1&2&4 \end{pmatrix} \in\mathbb R^{4\times3}.

Matrisen er fortsatt høy og har full kolonnerang. Derfor er

A_2^\dagger=(A_2^\top A_2)^{-1}A_2^\top.

For disse dataene blir andregradstilpasningen

q_2(t)=2{,}05+1{,}55t-0{,}05t^2, \qquad \|A_2x-b\|_2=\frac{\sqrt5}{10}\approx0{,}224.

Et tredjegradspolynom legger til enda en kolonne:

A_3= \begin{pmatrix} 1&-1&1&-1\\ 1&0&0&0\\ 1&1&1&1\\ 1&2&4&8 \end{pmatrix} \in\mathbb R^{4\times4}.

De fire inputverdiene er forskjellige. Derfor er denne kvadratiske Vandermonde-matrisen inverterbar. Dette er den viktige endringen:

A_3^\dagger=A_3^{-1}.

For denne numeriske matrisen er

A_3^\dagger=A_3^{-1} =\begin{pmatrix} 0&1&0&0\\ -1/3&-1/2&1&-1/6\\ 1/2&-1&1/2&0\\ -1/6&1/2&-1/2&1/6 \end{pmatrix}.

Tredjegradspolynomet interpolerer dermed alle fire datapunktene eksakt:

q_3(t)=\frac{11}{5}+\frac43t-\frac3{10}t^2+\frac16t^3, \qquad \|A_3x-b\|_2=0.

Null feil i disse fire punktene garanterer ikke bedre prediksjoner mellom eller utenfor dem. Det betyr bare at et tredjegradspolynom har nøyaktig fire koeffisienter til de fire interpolasjonskravene.

Hvorfor disse er inverser. De høye matrisene $A$ og $A_2$ har full kolonnerang, så pseudoinversene deres er venstreinverser. Den kvadratiske fullrangsmatrisen $A_3$ er annerledes: Pseudoinversen er den vanlige tosidige inversen.

Slik bekrefter du dem. For de høye tilpasningene kontrollerer du $A^\dagger A=I_2$ , $A_2^\dagger A_2=I_3$ og residualortogonalitet. For den kvadratiske matrisen i tredjegradsmodellen gir direkte multiplikasjon i begge rekkefølger

\boxed{A_3^\dagger A_3=A_3A_3^\dagger=I_4}.

Hurtigsjekk 23. For $B$ , $c$ og $x^\dagger$ fra Hurtigsjekk 22: Beskriv $\operatorname{range}(B)$ med koordinater, og bruk residualen til å forklare hvorfor $Bx^\dagger$ er punktet i kolonnerommet som ligger nærmest $c$ . Forklar hvorfor $B^\dagger$ teller som en invers for denne høye matrisen, og oppgi de avsluttende matrise- og residualkontrollene.

Løsning

Steg 1: Beskriv de mulige outputene.

\operatorname{range}(B) =\left\{ \begin{pmatrix}\alpha\\\beta\\\alpha+\beta\end{pmatrix} :\alpha,\beta\in\mathbb R \right\}.

Steg 2: Bruk residualtesten.

Fra forrige sjekk har vi

Bx^\dagger =\begin{pmatrix}4/3\\7/3\\11/3\end{pmatrix}, \qquad r=\begin{pmatrix}-1/3\\-1/3\\1/3\end{pmatrix}.

Siden $B^\top r=0$ , står $r$ vinkelrett på begge retningene som spenner opp kolonnerommet. Derfor kan ingen annen mulig output ligge nærmere $c$ .

Hvorfor dette er en invers. Siden $B$ har full kolonnerang, er $B^\dagger B=I_2$ : $B^\dagger$ er en venstreinvers på koeffisientvektorer.

Slik bekrefter du det. Matrisekontrollen er $B^\dagger B=I_2$ , som ble regnet ut i Hurtigsjekk 21. Datakontrollen er $B^\top r=0$ , som ble regnet ut over. Produktet $BB^\dagger$ er en symmetrisk projeksjon på $\operatorname{range}(B)$ .

Brede matriser: løsningen med minst norm

Anta at

A\in\mathbb R^{m\times n}, \qquad m<n, \qquad \operatorname{rank}(A)=m.

Matrisen har flere kolonner enn rader og full radrang. Med redusert SVD er

A^\dagger=V\Sigma^{-1}U^\top \in\mathbb R^{n\times m}.

Nå er identitetene snudd sammenlignet med den høye matrisen:

AA^\dagger=I_m, \qquad A^\dagger A=VV^\top=P_{\ker(A)^\perp}.

Et underbestemt system har flere ukjente enn ligninger. Under antakelsen om full radrang er hver $b\in\mathbb R^m$ oppnåelig, så systemet er alltid konsistent. Rang–nullitet gir dessuten

\dim\ker(A)=n-m>0,

så det finnes alltid uendelig mange eksakte løsninger. Pseudoinversen løser

\min_x\|x\|_2 \qquad \text{slik at }Ax=b.

Se dette i praksis

Gjennomregnet minieksempel 24. Finn pseudoinversen til den brede matrisen

A=\begin{pmatrix} 1&0&1\\ 0&1&1 \end{pmatrix}.

Bygg først den lille $2\times2$ -matrisen

AA^\top =\begin{pmatrix}2&1\\1&2\end{pmatrix}.

Inversen er

(AA^\top)^{-1} =\frac13\begin{pmatrix}2&-1\\-1&2\end{pmatrix}.

Dermed

A^\dagger =A^\top(AA^\top)^{-1} =\frac13\begin{pmatrix} 2&-1\\ -1&2\\ 1&1 \end{pmatrix}.

Pseudoinversen har form $3\times2$ . Riktig kontroll for denne fulle radrangen er

AA^\dagger =\frac13 \begin{pmatrix}1&0&1\\0&1&1\end{pmatrix} \begin{pmatrix}2&-1\\-1&2\\1&1\end{pmatrix} =\frac13\begin{pmatrix}3&0\\0&3\end{pmatrix} =I_2.

Hvorfor dette er en invers. Identiteten $AA^\dagger=I_2$ gjør $A^\dagger$ til en høyreinvers: Den gjenskaper enhver mulig output eksakt.

Slik bekrefter du det. I tillegg til multiplikasjonen over kontrollerer du at

A^\dagger A =\frac13\begin{pmatrix} 2&-1&1\\ -1&2&1\\ 1&1&2 \end{pmatrix}

er symmetrisk. Dette er den ortogonale projeksjonen som fjerner inputkomponenter i $\ker(A)$ .

Hurtigsjekk 24. La

B=\begin{pmatrix} 1&0&1\\ 0&1&-1 \end{pmatrix}.

Finn $B^\dagger$ med $B^\top(BB^\top)^{-1}$ , oppgi dimensjonen og kontroller $BB^\dagger=I_2$ . Forklar hvorfor dette gjør $B^\dagger$ til en invers i det brede tilfellet, og bekreft at $B^\dagger B$ er en symmetrisk projeksjon.

Løsning

Steg 1: Bygg og inverter Gram-matrisen.

BB^\top =\begin{pmatrix}2&-1\\-1&2\end{pmatrix}, \qquad (BB^\top)^{-1} =\frac13\begin{pmatrix}2&1\\1&2\end{pmatrix}.

Steg 2: Multipliser fra venstre med $B^\top$ .

B^\dagger =\frac13\begin{pmatrix} 2&1\\ 1&2\\ 1&-1 \end{pmatrix} \in\mathbb R^{3\times2}.

Steg 3: Kontroller høyreinversen.

BB^\dagger =\frac13\begin{pmatrix}3&0\\0&3\end{pmatrix} =I_2.

Hvorfor dette er en invers. Identiteten $BB^\dagger=I_2$ sier at $B^\dagger$ er en høyreinvers: Hvis vi først bruker $B^\dagger$ og deretter $B$ , får vi enhver outputvektor uendret tilbake.

Slik bekrefter du det. I motsatt rekkefølge får vi

B^\dagger B =\frac13\begin{pmatrix} 2&1&1\\ 1&2&-1\\ 1&-1&2 \end{pmatrix},

som er symmetrisk. Dermed er dette den ortogonale projeksjonen på $\ker(B)^\perp$ , mens $BB^\dagger=I_2$ bekrefter høyreinversegenskapen.

Se dette i praksis

Gjennomregnet minieksempel 25. Løs

Ax=b, \qquad b=\begin{pmatrix}3\\3\end{pmatrix},

med matrisen fra minieksempel 24. Pseudoinversen gir

x^\dagger=A^\dagger b =\frac13\begin{pmatrix} 2&-1\\ -1&2\\ 1&1 \end{pmatrix} \begin{pmatrix}3\\3\end{pmatrix} =\begin{pmatrix}1\\1\\2\end{pmatrix}.

Dette er en eksakt løsning:

Ax^\dagger =\begin{pmatrix}1+2\\1+2\end{pmatrix} =\begin{pmatrix}3\\3\end{pmatrix} =b.

Men den er ikke den eneste. Alle løsninger kan skrives

x =\begin{pmatrix}1\\1\\2\end{pmatrix} +t\begin{pmatrix}-1\\-1\\1\end{pmatrix}, \qquad t\in\mathbb R.

Den siste vektoren ligger i kjernen til $A$ . Dessuten er den ortogonal på $x^\dagger$ , så

\|x\|_2^2 =\|x^\dagger\|_2^2 +3t^2 =6+3t^2.

Normen er minst for $t=0$ .

Hvorfor dette er en invers. Minieksempel 24 viste $AA^\dagger=I_2$ , så $A^\dagger$ er en høyreinvers og garanterer $Ax^\dagger=b$ for enhver $b\in\mathbb R^2$ .

Slik bekrefter du det. Her er

x^\dagger\cdot\begin{pmatrix}-1\\-1\\1\end{pmatrix} =-1-1+2=0.

Høyreinverskontrollen bekrefter eksakthet, og denne ortogonaliteten til $\ker(A)$ bekrefter at ingen kjernevektor kan gjøre løsningen kortere.

Hurtigsjekk 25. Bruk

B=\begin{pmatrix}1&0&1\\0&1&-1\end{pmatrix}, \qquad c=\begin{pmatrix}1\\1\end{pmatrix}.

Finn $x^\dagger=B^\dagger c$ . Skriv deretter alle eksakte løsninger som $x^\dagger+t z$ , der $z$ spenner opp $\ker(B)$ , og forklar hvorfor $t=0$ gir minst norm. Forklar hvorfor $B^\dagger$ teller som en invers i dette brede tilfellet, og oppgi både eksakthets- og minstenormskontrollen.

Løsning

Steg 1: Finn pseudoinversløsningen.

x^\dagger =\frac13\begin{pmatrix}2&1\\1&2\\1&-1\end{pmatrix} \begin{pmatrix}1\\1\end{pmatrix} =\begin{pmatrix}1\\1\\0\end{pmatrix}.

Steg 2: Finn kjernefriheten.

Ligningene er $x_1+x_3=1$ og $x_2-x_3=1$ . Derfor

x =\begin{pmatrix}1\\1\\0\end{pmatrix} +t\begin{pmatrix}-1\\1\\1\end{pmatrix}.

Steg 3: Sammenlign normene.

Kjernevektoren er ortogonal på $x^\dagger$ fordi $-1+1+0=0$ . Dermed

\|x\|_2^2=2+3t^2,

som er minst for $t=0$ .

Hvorfor dette er en invers. Hurtigsjekk 24 ga $BB^\dagger=I_2$ , så $B^\dagger$ er en høyreinvers og $Bx^\dagger=c$ er eksakt.

Slik bekrefter du det. Kontroller $BB^\dagger=I_2$ og

x^\dagger\cdot\begin{pmatrix}-1\\1\\1\end{pmatrix} =-1+1+0=0.

Den første testen bekrefter inversegenskapen; den andre bekrefter minst norm blant alle eksakte løsninger.

Bevisideen for minst norm, én linje om gangen

Sett

x^\dagger=A^\dagger b.

Siden $A$ har full radrang,

Ax^\dagger=AA^\dagger b=b.

Altså er $x^\dagger$ en eksakt løsning. La $y$ være en annen eksakt løsning. Da

Ay=b

og derfor

A^\dagger Ay=A^\dagger b=x^\dagger.

Men $A^\dagger A$ er en ortogonal projeksjon. En projeksjon kan ikke gjøre en vektor lengre:

\|x^\dagger\|_2 =\|A^\dagger Ay\|_2 \le \|y\|_2.

Dermed er pseudoinversløsningen den korteste eksakte løsningen.

Se dette i praksis

Gjennomregnet minieksempel 26. For systemet i minieksempel 25 er

x^\dagger=\begin{pmatrix}1\\1\\2\end{pmatrix}.

En annen eksakt løsning er

y=\begin{pmatrix}3\\3\\0\end{pmatrix}.

Forskjellen er en kjernevektor:

y-x^\dagger =\begin{pmatrix}2\\2\\-2\end{pmatrix}, \qquad A(y-x^\dagger)=0.

Sammenlign normene:

\|x^\dagger\|_2=\sqrt6, \qquad \|y\|_2=\sqrt{18}.

Begge treffer dataene nøyaktig. Pseudoinversen vinner bare fordi den unngår den unødvendige kjernekomponenten.

Hvorfor dette er en invers. Den samme identiteten $AA^\dagger=I_2$ fra minieksempel 24 gjør $A^\dagger$ til en høyreinvers, så begge vektorene gjenskaper den ønskede outputen.

Slik bekrefter du det. Forskjellen ligger i $\ker(A)$ , og

(x^\dagger)^\top(y-x^\dagger)=2+2-4=0.

Høyreinversidentiteten bekrefter eksakthet, mens ortogonaliteten til kjernen bekrefter at $x^\dagger$ har minst norm.

Hurtigsjekk 26. For systemet i Hurtigsjekk 25 er

x^\dagger=\begin{pmatrix}1\\1\\0\end{pmatrix}.

Vis at

y=\begin{pmatrix}0\\2\\1\end{pmatrix}

også er en løsning. Finn $y-x^\dagger$ , kontroller at forskjellen ligger i $\ker(B)$ , og sammenlign normene. Forklar hvorfor $B^\dagger$ teller som en invers, og oppgi sluttkontrollene for eksakthet og minst norm.

Løsning

Steg 1: Kontroller begge løsningene.

By =\begin{pmatrix}0+1\\2-1\end{pmatrix} =\begin{pmatrix}1\\1\end{pmatrix} =c.

Steg 2: Finn kjernekomponenten og normene.

y-x^\dagger =\begin{pmatrix}-1\\1\\1\end{pmatrix}, \qquad B(y-x^\dagger)=0.

Videre er

\|x^\dagger\|_2=\sqrt2, \qquad \|y\|_2=\sqrt5.

Den ekstra kjernekomponenten endrer ikke outputen, men gjør løsningen lengre.

Hvorfor dette er en invers. Siden $BB^\dagger=I_2$ , er $B^\dagger$ en høyreinvers og $Bx^\dagger=c$ er eksakt.

Slik bekrefter du det. I tillegg til $BB^\dagger=I_2$ kontrollerer du

(x^\dagger)^\top(y-x^\dagger)=-1+1+0=0.

Forskjellen ligger i $\ker(B)$ , så denne ortogonaliteten viser at den bare kan øke normen.

Til venstre projiseres data på kolonnerommet i et overbestemt problem. Til høyre velges punktet med minst norm blant mange eksakte løsninger i et underbestemt problem.Full størrelse / Full size ↗

Generell rangmangel: best tilpasning først, minst norm deretter

Dette er punktet der form alene slutter å være nok. En matrise kan være høy, bred eller kvadratisk og likevel ha rangmangel.

Behold derfor én sikker regel. Hvis

A=\sum_{i=1}^r\sigma_i u_iv_i^\top =U_r\Sigma_rV_r^\top

er den kompakte SVD-en, så

A^\dagger =\sum_{i=1}^r\frac1{\sigma_i}v_iu_i^\top =V_r\Sigma_r^{-1}U_r^\top.

Bare positive singulærverdier inverteres.

Se dette i praksis

Gjennomregnet minieksempel 27. La

A=\begin{pmatrix}1&2\\2&4\end{pmatrix}, \qquad b=\begin{pmatrix}3\\6\end{pmatrix}.

Matrisen er kvadratisk, men ikke invertibel: Den andre kolonnen er to ganger den første, så $\operatorname{rank}(A)=1$ .

Dette er også en symmetrisk positiv semidefinit rang-1-matrise. Fra SVD-eksemplet tidligere har vi

\sigma_1=5, \qquad u_1=v_1 =\frac1{\sqrt5}\begin{pmatrix}1\\2\end{pmatrix}.

Derfor

A^\dagger =\frac1{\sigma_1}v_1u_1^\top =\frac1{25}\begin{pmatrix}1&2\\2&4\end{pmatrix}.

Løsningen blir

x^\dagger=A^\dagger b =\frac1{25}\begin{pmatrix}1&2\\2&4\end{pmatrix} \begin{pmatrix}3\\6\end{pmatrix} =\begin{pmatrix}3/5\\6/5\end{pmatrix}.

Multipliser tilbake:

Ax^\dagger =\begin{pmatrix}3\\6\end{pmatrix} =b.

Feilen er null fordi $b$ ligger i verdirommet:

b=3\begin{pmatrix}1\\2\end{pmatrix}.

Det finnes likevel uendelig mange løsninger:

x =\begin{pmatrix}3/5\\6/5\end{pmatrix} +t\begin{pmatrix}-2\\1\end{pmatrix}.

Kjernevektoren står vinkelrett på $x^\dagger$ . Derfor velger pseudoinversen $t=0$ og dermed løsningen med minst norm.

Hvorfor dette er en invers. Ingen vanlig invers finnes, men $A^\dagger$ reverserer den ene positive singulærretningen og lar den kollapsede retningen være null. Det er nettopp rollen til den generaliserte inversen.

Slik bekrefter du det. Siden $A^2=5A$ , er

AA^\dagger=A^\dagger A=\frac15A

symmetrisk, og dette gir $AA^\dagger A=A$ og $A^\dagger AA^\dagger=A^\dagger$ . Dermed er alle fire Moore–Penrose-betingelsene kontrollert.

Hurtigsjekk 27. La

C=\begin{pmatrix}4&2\\2&1\end{pmatrix}, \qquad d=\begin{pmatrix}8\\4\end{pmatrix}.

a) Vis raskt at $C$ har rang 1 og er positiv semidefinit.

b) Bruk $\sigma_1=5$ til å finne $C^\dagger$ .

c) Finn $x^\dagger=C^\dagger d$ , kontroller $Cx^\dagger=d$ , og beskriv alle løsninger.

d) Forklar hvorfor $C^\dagger$ teller som en generalisert invers, og bekreft det med rekonstruksjons- og symmetrikontrollene.

Løsning

Steg 1: Se rang-1-mønsteret.

C=\begin{pmatrix}2\\1\end{pmatrix} \begin{pmatrix}2&1\end{pmatrix}.

Dermed er $C$ symmetrisk positiv semidefinit med rang 1 og eneste positive singulærverdi

\left\|\begin{pmatrix}2\\1\end{pmatrix}\right\|_2^2=5.

Steg 2: Inverter den positive singulærverdien.

C^\dagger =\frac1{25}\begin{pmatrix}4&2\\2&1\end{pmatrix}.

Steg 3: Løs og finn kjernefriheten.

x^\dagger=C^\dagger d =\begin{pmatrix}8/5\\4/5\end{pmatrix}.

Kontrollen regnes helt ut:

Cx^\dagger =\begin{pmatrix}4&2\\2&1\end{pmatrix} \begin{pmatrix}8/5\\4/5\end{pmatrix} =\begin{pmatrix}40/5\\20/5\end{pmatrix} =\begin{pmatrix}8\\4\end{pmatrix} =d.

Siden

\ker(C)=\operatorname{span}\left\{\begin{pmatrix}-1\\2\end{pmatrix}\right\},

er alle løsninger

x=\begin{pmatrix}8/5\\4/5\end{pmatrix} +t\begin{pmatrix}-1\\2\end{pmatrix}.

Hvorfor dette er en invers. $C$ har ingen vanlig invers, men $C^\dagger$ reverserer den ene positive singulærretningen og lar $\ker(C)$ være null.

Slik bekrefter du det. Siden $C^2=5C$ , er

CC^\dagger=C^\dagger C=\frac15C

symmetrisk. Derfor er $CC^\dagger C=C$ og $C^\dagger CC^\dagger=C^\dagger$ , som bekrefter alle fire Penrose-ligningene. Dessuten er

(x^\dagger)^\top\begin{pmatrix}-1\\2\end{pmatrix} =-\frac85+\frac85=0,

som bekrefter minstenormsvalget.

Moore–Penrose-inversen kjennetegnes entydig av fire ligninger:

AA^\dagger A=A, \qquad A^\dagger AA^\dagger=A^\dagger,

(AA^\dagger)^\top=AA^\dagger, \qquad (A^\dagger A)^\top=A^\dagger A.

De to første sier «rekonstruer det som kan rekonstrueres». De to siste sier at projektorene er ortogonale, ikke skjeve.

Se dette i praksis

Gjennomregnet minieksempel 28. For rang-1-matrisen fra minieksempel 27 er

A^\dagger=\frac1{25}A.

Siden $A^2=5A$ , får vi

AA^\dagger=A^\dagger A =\frac15A =\frac15\begin{pmatrix}1&2\\2&4\end{pmatrix}.

Dette er den ortogonale projeksjonen på

\operatorname{span}\left\{\begin{pmatrix}1\\2\end{pmatrix}\right\}.

Den er symmetrisk. Dessuten

AA^\dagger A =\frac15A^2 =A,

og tilsvarende $A^\dagger AA^\dagger=A^\dagger$ .

Hvorfor dette er en invers. Selv om $A$ er singulær, rekonstruerer $A^\dagger$ alt i den overlevende singulærretningen og bruker ortogonale projeksjoner i retningene som ikke kan inverteres.

Slik bekrefter du det. De to rekonstruksjonsligningene over og symmetrien til både $AA^\dagger$ og $A^\dagger A$ er akkurat de fire Moore–Penrose-ligningene.

Hurtigsjekk 28. Bruk $C$ og $C^\dagger$ fra Hurtigsjekk 27. Finn $CC^\dagger$ og $C^\dagger C$ , kontroller alle fire Penrose-ligningene, og bruk dem til å forklare hvorfor $C^\dagger$ teller som en generalisert invers.

Løsning

Steg 1: Finn de to projektorproduktene.

Siden $C^2=5C$ ,

CC^\dagger=C^\dagger C =\frac15C =\frac15\begin{pmatrix}4&2\\2&1\end{pmatrix}.

Begge er symmetriske.

Steg 2: Kontroller rekonstruksjonene.

CC^\dagger C =\frac15C^2=C,

C^\dagger CC^\dagger =\frac1{25}C\,\frac15C =\frac1{125}C^2 =\frac1{25}C =C^\dagger.

Dermed holder alle fire Penrose-ligningene.

Hvorfor dette er en invers. Rekonstruksjonsidentitetene viser at vi rekonstruerer alt som kan rekonstrueres når vi bruker $C$ , så $C^\dagger$ , og så den opprinnelige avbildningen. De symmetriske produktene gjør operasjonene til ortogonale projeksjoner.

Slik bekrefter du det. Kontroller akkurat de fire ligningene som er regnet ut over: to rekonstruksjonsidentiteter og to symmetriidentiteter. At alle fire holder samtidig, bekrefter entydig Moore–Penrose-inversen.

For vilkårlige $A$ og $b$ følger $x^\dagger=A^\dagger b$ alltid to prioriteringer:

Minimer $\|Ax-b\|_2$ .
Blant alle minimisatorer, velg den med minst $\|x\|_2$ .

Se dette i praksis

Gjennomregnet minieksempel 29. Behold

A=\begin{pmatrix}1&2\\2&4\end{pmatrix},

men bytt dataene til

\widetilde b=\begin{pmatrix}1\\0\end{pmatrix}.

Nå ligger ikke $\widetilde b$ på linjen

\operatorname{span}\left\{\begin{pmatrix}1\\2\end{pmatrix}\right\}.

Pseudoinversen gir

\widetilde x =A^\dagger\widetilde b =\begin{pmatrix}1/25\\2/25\end{pmatrix}.

Den best mulige outputen er

A\widetilde x =AA^\dagger\widetilde b =\begin{pmatrix}1/5\\2/5\end{pmatrix}.

Residualen er

\widetilde b-A\widetilde x =\begin{pmatrix}4/5\\-2/5\end{pmatrix},

med norm

\left\|\widetilde b-A\widetilde x\right\|_2 =\frac2{\sqrt5}.

Den står vinkelrett på verdirommet. Alle minste-kvadraters minimisatorer er

x=\widetilde x+t\begin{pmatrix}-2\\1\end{pmatrix},

og pseudoinversen velger igjen $t=0$ .

Hvorfor dette er en invers. Den samme $A^\dagger$ som ble kontrollert i minieksempel 28, reverserer den overlevende singulærretningen. For uoppnåelige data gir $AA^\dagger$ den nærmeste mulige outputen i stedet for å late som en tosidig invers finnes.

Slik bekrefter du det. De fire Penrose-kontrollene står i minieksempel 28. For denne datavektoren kontrollerer du i tillegg

A^\top\left(\widetilde b-A\widetilde x\right) =\begin{pmatrix}1&2\\2&4\end{pmatrix} \begin{pmatrix}4/5\\-2/5\end{pmatrix} =\begin{pmatrix}0\\0\end{pmatrix}, \qquad \widetilde x^\top\begin{pmatrix}-2\\1\end{pmatrix} =-\frac2{25}+\frac2{25}=0.

Den første bekrefter beste tilpasning; den andre bekrefter minst norm.

Hurtigsjekk 29. Bruk

C=\begin{pmatrix}4&2\\2&1\end{pmatrix}, \qquad e=\begin{pmatrix}0\\1\end{pmatrix}.

Finn $x^\dagger=C^\dagger e$ , den best mulige outputen $Cx^\dagger$ , residualen og residualnormen. Beskriv til slutt alle minste-kvadraters minimisatorer. Forklar hvorfor $C^\dagger$ teller som en generalisert invers, og oppgi både matrise- og løsningskontrollene som bekrefter den.

Løsning

Steg 1: Finn pseudoinversløsningen.

x^\dagger =\frac1{25}\begin{pmatrix}4&2\\2&1\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix} =\begin{pmatrix}2/25\\1/25\end{pmatrix}.

Steg 2: Finn tilpasning og residual.

Cx^\dagger =\begin{pmatrix}2/5\\1/5\end{pmatrix}, \qquad r=e-Cx^\dagger =\begin{pmatrix}-2/5\\4/5\end{pmatrix}.

Dermed

\|r\|_2=\frac2{\sqrt5}.

Steg 3: Legg til kjernefriheten.

Alle beste tilpasninger er

x=\begin{pmatrix}2/25\\1/25\end{pmatrix} +t\begin{pmatrix}-1\\2\end{pmatrix}.

Pseudoinversen velger $t=0$ , fordi kjernevektoren er ortogonal på $x^\dagger$ og alle andre valg øker normen.

Hvorfor dette er en invers. Hurtigsjekk 28 bekreftet alle fire Penrose-ligningene for denne $C^\dagger$ . Dermed er den den entydige generaliserte inversen som bruker ortogonale projeksjoner.

Slik bekrefter du det. Bruk de fire matriseidentitetene fra Hurtigsjekk 28 om igjen. For løsningen kontrollerer du numerisk at

C^\top r =\begin{pmatrix}4&2\\2&1\end{pmatrix} \begin{pmatrix}-2/5\\4/5\end{pmatrix} =\begin{pmatrix}0\\0\end{pmatrix}, \qquad (x^\dagger)^\top\begin{pmatrix}-1\\2\end{pmatrix} =-\frac2{25}+\frac2{25}=0.

Disse to testene bekrefter prioriteringene beste tilpasning og minst norm.

Eksempel fra den håndregnede SVD-en

Pseudoinversen bruker de samme singulærretningene som det fulle SVD-eksemplet, men reverserer bare de positive strekkene og snur rekkefølgen på ytterfaktorene. Åpne utregningen for hele matriseproduktet og begge projeksjonskontrollene.

Full utregning: pseudoinversen til den håndregnede matrisen

For den korrigerte forelesningsmatrisen

A=\begin{pmatrix}1&3\\2&2\\3&1\end{pmatrix}

bruker vi SVD-en fra Del 2.

Steg 1: inverter bare de positive singulærverdiene.

\Sigma_r^{-1} =\begin{pmatrix}1/\sqrt{24}&0\\0&1/2\end{pmatrix}.

Steg 2: snu rekkefølgen på singulærvektorfaktorene. Formelen er $A^\dagger=V_r\Sigma_r^{-1}U_r^\top$ , ikke $U_r\Sigma_r^{-1}V_r^\top$ . Dimensjonene er

(2\times2)(2\times2)(2\times3)=2\times3,

som er den motsatte formen av $A$ .

Steg 3: sett inn matrisene.

A^\dagger =\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} \begin{pmatrix}1/\sqrt{24}&0\\0&1/2\end{pmatrix} \begin{pmatrix}1/\sqrt3&1/\sqrt3&1/\sqrt3\\-1/\sqrt2&0&1/\sqrt2\end{pmatrix}.

Multiplikasjon gir

A^\dagger =\begin{pmatrix}-1/6&1/12&1/3\\1/3&1/12&-1/6\end{pmatrix}.

Steg 4: kontroller identiteten som passer for en høy matrise med full kolonnerang.

A^\dagger A=I_2.

Det motsatte produktet er en $3\times3$ -projeksjon, ikke $I_3$ :

AA^\dagger =\begin{pmatrix}5/6&1/3&-1/6\\1/3&1/3&1/3\\-1/6&1/3&5/6\end{pmatrix}.

Det projiserer data på det todimensjonale kolonnerommet til $A$ .

Uavhengig Axia-kontroll. For $\widetilde A=\begin{pmatrix}2&0\\0&2\\1&1\end{pmatrix}$ inverterer vi $\sqrt6$ og $2$ i den uavhengige SVD-en fra Del 2. Det gir

\widetilde A^\dagger =\begin{pmatrix}5/12&-1/12&1/6\\-1/12&5/12&1/6\end{pmatrix},

og direkte multiplikasjon bekrefter $\widetilde A^\dagger\widetilde A=I_2$ . Begge eksemplene viser at det er metoden, ikke ett bestemt sett med tall, som skal gjenbrukes.

Hvorfor dette er en invers. Begge matrisene er høye og har full kolonnerang. Derfor er pseudoinversene venstreinverser som gjenfinner enhver vektor i det todimensjonale koeffisientrommet eksakt.

Slik bekrefter du det. Multipliser i venstreinversrekkefølgen og få $A^\dagger A=I_2$ og $\widetilde A^\dagger\widetilde A=I_2$ . I motsatt rekkefølge kontrollerer du at $AA^\dagger$ og $\widetilde A\widetilde A^\dagger$ er symmetriske projeksjoner. For en minste-kvadraters datavektor skal den tilhørende residualen også oppfylle $A^\top r=0$ .

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 5 · Trunkert SVD og L-kurvemetoden

Små singulærverdier og støy

Hvorfor er støy et problem?

Pseudoinversen deler på singulærverdier.

Det er ufarlig for store verdier. For bittesmå verdier kan det være katastrofalt.

La de målte dataene være

b^\delta=b+n^\delta, \qquad \|n^\delta\|_2\le\delta,

og la $x^\dagger=A^\dagger b$ . Den uregulariserte løsningen fra de støyete dataene er

x^\delta=A^\dagger b^\delta =x^\dagger+A^\dagger n^\delta.

Når $r\ge1$ , er $\|A^\dagger\|_2=1/\sigma_r$ , så den eksakte formelen for verst mulig forsterkning er

\max_{\|e\|_2\le\delta}\|A^\dagger e\|_2 = \max_{\|n^\delta\|_2\le\delta} \|x^\delta-x^\dagger\|_2 =\frac{\delta}{\sigma_r}.

Se dette i praksis

Gjennomregnet minieksempel 30. Hvis $\sigma_r=0{,}001$ og $\delta=0{,}01$ , er den verst mulige forsterkningen

\frac{\delta}{\sigma_r}=\frac{0{,}01}{0{,}001}=10.

En datafeil med størrelse $0{,}01$ kan altså skape en løsningsfeil med størrelse $10$ .

Hurtigsjekk 30. Finn den verste feilgrensen når $\sigma_r=0{,}002$ og $\delta=0{,}006$ .

Løsning

Fasit:

\frac{\delta}{\sigma_r}=\frac{0{,}006}{0{,}002}=3.

Dermed kan datastøy med norm høyst $0{,}006$ gi en løsningsfeil så stor som $3$ i den verst orienterte retningen.

Forklaring: Operatornormen til pseudoinversen er $1/\sigma_r$ , så den farligste støyen peker langs den tilhørende venstre singulærretningen.

Trunkering av små singulærverdier

Løsningen er bevisst: Vi slutter å invertere retninger som er for ustabile.

For en terskel $\varepsilon>0$ definerer vi

A_\varepsilon =\sum_{\sigma_i\ge\varepsilon}\sigma_i u_iv_i^\top, \qquad A_\varepsilon^\dagger =\sum_{\sigma_i\ge\varepsilon}\frac1{\sigma_i}v_iu_i^\top.

For støyfrie data definerer vi $x_\varepsilon=A_\varepsilon^\dagger b$ ; for målte data definerer vi $x_\varepsilon^\delta=A_\varepsilon^\dagger b^\delta$ .

Terskelen $\varepsilon$ er tillitsgrensen. Verdier over grensen brukes; verdier under grensen forkastes.

Se dette i praksis

Gjennomregnet minieksempel 31. Anta at singulærverdiene er $5,1,0{,}01$ og velg $\varepsilon=0{,}1$ . Vi beholder $5$ og $1$ , men forkaster $0{,}01$ . Den trunkerte pseudoinversen bruker $1/5$ og $1$ , men unngår den farlige faktoren $1/0{,}01=100$ .

Hurtigsjekk 31. Singulærverdiene er $8,0{,}4,0{,}02$ , og $\varepsilon=0{,}1$ . Hvilke verdier beholdes, og hvilke inverse faktorer står i $A_\varepsilon^\dagger$ ?

Løsning

Fasit: Behold $8$ og $0{,}4$ , forkast $0{,}02$ , og bruk faktorene $1/8$ og $1/0{,}4=2{,}5$ .

Forklaring: Bare singulærverdier som er minst $\varepsilon=0{,}1$ , regnes som pålitelige. Den farlige faktoren $1/0{,}02=50$ tas derfor ikke med.

Oppdeling av feilen

Det er her notasjonen blir tung. Hold to bokser i hodet: Trunkering gir skjevhet selv med støyfrie data, mens beholdte små singulærverdier forsterker målestøy.

Hvis $b=Ax^\dagger$ , er

\|x_\varepsilon^\delta-x^\dagger\|_2 \le \|(I-A_\varepsilon^\dagger A)x^\dagger\|_2 +\frac{\delta}{\varepsilon}.

Det første leddet er informasjon som bevisst forkastes ved trunkering. Det andre er støyforsterkning. Liten $\varepsilon$ mister mindre informasjon, men forsterker mer støy; stor $\varepsilon$ gjør det motsatte.

Se dette i praksis

Gjennomregnet minieksempel 32. La $\delta=0{,}01$ . Med $\varepsilon=0{,}001$ kan støyleddet bli så stort som $10$ . Med $\varepsilon=0{,}1$ er det begrenset av $0{,}1$ . Den større terskelen er mer stabil, men kan forkaste flere nyttige retninger.

Hurtigsjekk 32. La $\delta=0{,}02$ . Sammenlign støygrensene for $\varepsilon=0{,}01$ og $\varepsilon=0{,}2$ .

Løsning

Fasit:

\frac{0{,}02}{0{,}01}=2, \qquad \frac{0{,}02}{0{,}2}=0{,}1.

Den større terskelen gir den minste støygrensen, men kan gi større trunkeringsfeil.

Forklaring: Støyleddet er $\delta/\varepsilon$ , så økningen fra $0{,}01$ til $0{,}2$ reduserer dette leddet fra $2$ til $0{,}1$ .

Regulariseringsfeil uttrykt med koeffisienter

Minimumsnormløsningen ligger i $\operatorname{span}\{v_1,\ldots,v_r\}$ og kan skrives

x^\dagger=\sum_{i=1}^r x_i^\dagger v_i.

Hvis terskelen forkaster alle $\sigma_i<\varepsilon$ , er

\|A_\varepsilon^\dagger b-x^\dagger\|_2 =\left(\sum_{\sigma_i<\varepsilon}|x_i^\dagger|^2\right)^{1/2}.

Dette er ikke støyfeil. Det er nyttig innhold i løsningen som vi selv valgte å fjerne.

Se dette i praksis

Gjennomregnet minieksempel 33. La

x^\dagger=3v_1+4v_2+12v_3

og anta at terskelen forkaster den tredje retningen. Da er $x_\varepsilon=3v_1+4v_2$ , og regulariseringsfeilen er $\|12v_3\|_2=12$ .

Hurtigsjekk 33. La $x^\dagger=5v_1+12v_2+4v_3$ med ortonormale $v_i$ , og forkast den tredje retningen. Finn den trunkerte løsningen og regulariseringsfeilen.

Løsning

Fasit:

x_\varepsilon=5v_1+12v_2, \qquad x^\dagger-x_\varepsilon=4v_3.

Siden $v_3$ har lengde $1$ , er feilen $4$ .

Forklaring: Ortonormale retninger følger Pytagoras, og den eneste forkastede koeffisienten er $4$ .

Valg av $k$ i stedet for $\varepsilon$

I stedet for en terskel kan vi beholde nøyaktig de første $k$ singulærretningene:

A_k^\dagger=\sum_{i=1}^k\frac1{\sigma_i}v_iu_i^\top, \qquad x_\delta^{(k)}=A_k^\dagger b^\delta.

Da er

\|x_\delta^{(k)}\|_2^2 =\sum_{i=1}^k \frac{|\langle u_i,b^\delta\rangle|^2}{\sigma_i^2},

så løsningsnormen er ikke-avtakende i $k$ . Etter at $u_1,\ldots,u_r$ er fullført til en ortonormal basis i datarommet, er

Ax_\delta^{(k)}-b^\delta =-\sum_{i=k+1}^{m}\langle u_i,b^\delta\rangle u_i,

så residualnormen er ikke-økende. Øvre grense er $m$ , dimensjonen til datarommet.

Se dette i praksis

Gjennomregnet minieksempel 34. For singulærverdiene $10,1,0{,}01$ bruker $k=1$ bare den sterkeste retningen, $k=2$ tar også med faktoren $1$ , og $k=3$ deler på $0{,}01$ og innfører faktoren $100$ . Større $k$ kan gi bedre tilpasning, men en mye mindre stabil løsning.

Hurtigsjekk 34. For singulærverdiene $6,0{,}5,0{,}02$ , oppgi de inverse faktorene som innføres ved $k=1,2,3$ , og identifiser det risikable trinnet.

Løsning

Fasit: Faktorene er $1/6$ ved $k=1$ , deretter $2$ ved $k=2$ , og til slutt $50$ ved $k=3$ . Det risikable trinnet er $k=3$ .

Forklaring: Den tredje retningen deler på $0{,}02$ , så støy i denne retningen kan forstørres med $50$ .

L-kurvemetoden

Se dette i praksis

Gjennomregnet minieksempel 35. Anta at vi har regnet ut

$k$	løsningsnorm	residual
1	1	10
2	2	4
3	4	2
4	20	1,8
5	100	1,7

Fram til $k=3$ blir residualen mye mindre, mens løsningen vokser moderat. Etter $k=3$ endres residualen nesten ikke, mens løsningsnormen eksploderer. Det sannsynlige hjørnet er $k=3$ .

Hurtigsjekk 35. Kun anvendelse: En ny tabell gir $(0{,}8,12)$ , $(1{,}5,5)$ , $(3,2{,}2)$ , $(18,2{,}0)$ og $(70,1{,}9)$ for $k=1,\ldots,5$ , der hvert par er (løsningsnorm, residual). Finn det sannsynlige hjørnet og begrunn valget. Dette er tolkningsøving, ikke eksamensregning.

Løsning

Fasit: Det sannsynlige hjørnet er $k=3$ .

Forklaring: Fra $k=1$ til $3$ faller residualen fra $12$ til $2{,}2$ , mens normen bare vokser fra $0{,}8$ til $3$ . Ved $k=4$ og $5$ blir residualen knapt mindre, men normen vokser til $18$ og $70$ .

Oppsummering

Hver reell matrise har en SVD $A=U\Sigma V^\top$ .
Singulærverdiene er ikke-negative kvadratrøtter av egenverdiene til $A^\top A$ eller $AA^\top$ .
De positive singulærverdiene bestemmer rang, verdirom, kjerne og matrise-normer.
Trunkert SVD gir den beste lavrang-approksimasjonen i både spektralnorm og Frobenius-norm.
$A^\dagger$ reverserer singulærretninger forskjellig fra null og gir minste-kvadraters løsningen med minst norm.
Små singulærverdier forsterker støy; trunkering bytter informasjon mot stabilitet.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 6 · Tensorer

Start med et fargebilde

Hva er en tensor?

𝓧 ∈ ℝ³ˣ⁴ˣ³

I numerisk matematikk er en tensor en flerveis tabell med tall. Et fargebilde er et konkret eksempel: én talltabell per fargekanal.

Orden forteller hvor mange koordinater en adresse trengerDet forteller ikke hvor mange tall som er lagret.

Skalarorden 0ett tall

Vektororden 1én indeks i

Matriseorden 2rad i, kolonne j

3-tensororden 3rad i, kolonne j, lag ℓ

Lag ℓ = 1 · rødLag ℓ = 2 · grønnLag ℓ = 3 · blå

: Kolonet betyr «denne indeksen får variere». En fiber har ett kolon; et snitt har to.

Adresse

Fiber · én indeks varierer

Snitt · én indeks er fast

𝓧 ∈ ℝ³ˣ⁴ˣ³

Dette er én 3 × 4 × 3-tensor: tre talltabeller som holdes samlet. De tre indeksretningene er rad i, kolonne j og fargelag ℓ.

0 frie → verdi1 fri → fiber2 frie → snitt

Laster interaktiv modell / Loading interactive model …

Motivasjon

Strukturerte data har ofte mer enn to naturlige retninger. Et gråtonebilde med $m\times n$ piksler kan lagres som én matrise

A\in[0,1]^{m\times n},

der $0$ betyr svart og $1$ betyr hvitt. Et fargebilde trenger derimot én matrise for hver fargekanal,

R,G,B\in[0,1]^{m\times n},

og hele bildet kan derfor samles som

\mathcal X\in[0,1]^{m\times n\times3}.

En film trenger røde, grønne og blå matriser for hvert bilde $i=1,\ldots,N$ , og får formen

\mathcal X\in[0,1]^{m\times n\times3\times N}.

Høyde, bredde, farge og tid er fire forskjellige modi, altså retninger i dataene. En romlig film kan i tillegg ha dybde og bli femdimensjonal.

Se dette i praksis

Et gråtonebilde med $2\times3$ piksler kan lagres som

A= \begin{pmatrix} 0&1&0{,}5\\ 1&0&0{,}25 \end{pmatrix}.

Et fargebilde med samme størrelse trenger tre slike tabeller,

R,G,B\in\mathbb R^{2\times3}.

I stedet for å behandle dem som tre løse matriser, legger vi dem i én tensor

\mathcal X\in\mathbb R^{2\times3\times3}.

Den første modusen er høyde, den andre er bredde, og den tredje velger fargekanal. Ett bildeobjekt har altså tre naturlige retninger samtidig.

Hurtigsjekk 36. En videosnutt har $4$ rader, $6$ kolonner, tre fargekanaler og $8$ bilder. Oppgi tensorens orden, form, betydningen av de fire modiene og antallet lagrede tall.

Løsning

Steg 1: Én indeks trengs for hver av retningene rad, kolonne, farge og tid. Tensoren har derfor orden $4$ .

Steg 2: Formen er

\mathcal X\in\mathbb R^{4\times6\times3\times8}.

Modus $1$ , $2$ , $3$ og $4$ betyr henholdsvis høyde, bredde, fargekanal og bildenummer.

Steg 3: Antallet tall er

4\cdot6\cdot3\cdot8=576.

Definisjon av en tensor

En matrise er en tensor av orden $2$ fordi hvert tall trenger to indekser. Generelt trenger en tensor av orden $d$ nøyaktig $d$ indekser for å angi adressen til ett tall.

Se dette i praksis

Et tall trenger ingen indeks:

x=7,

så det er en tensor av orden $0$ .

En vektor trenger én indeks:

x=\begin{pmatrix}2\\5\\1\end{pmatrix}, \qquad x_2=5,

så den har orden $1$ .

En matrise trenger to indekser:

A=\begin{pmatrix}1&4\\2&5\end{pmatrix}, \qquad a_{2,1}=2,

så den har orden $2$ .

En tensor $\mathcal X\in\mathbb R^{m\times n\times p}$ trenger tre indekser. Adressen $x_{2,1,3}$ betyr andre posisjon i modus $1$ , første posisjon i modus $2$ og tredje posisjon i modus $3$ .

Hurtigsjekk 37. Klassifiser $q=4$ , $v\in\mathbb R^5$ , $M\in\mathbb R^{3\times2}$ og $\mathcal Y\in\mathbb R^{3\times2\times4}$ . Hvor mange indekser trenger hvert objekt, og hva betyr $y_{2,1,4}$ ?

Løsning

Steg 1: $q$ er en skalar av orden $0$ , $v$ er en vektor av orden $1$ , $M$ er en matrise av orden $2$ , og $\mathcal Y$ er en tensor av orden $3$ .

Steg 2: De trenger henholdsvis null, én, to og tre indekser for å velge én oppføring.

Steg 3: $y_{2,1,4}$ er skalaren på posisjon $2$ i første modus, posisjon $1$ i andre modus og posisjon $4$ i tredje modus.

Eksempler på tensorordener

\begin{array}{c|c|c} d&\text{objekt}&\text{typisk rom}\\ \hline 0&\text{skalar}&x\in\mathbb R\\ 1&\text{vektor}&x\in\mathbb R^n\\ 2&\text{matrise}&A\in\mathbb R^{m\times n}\\ 3&\text{tredjeordens tensor}&\mathcal X\in\mathbb R^{m\times n\times p} \end{array}

Orden er antallet indekser, ikke antallet tall, antallet lag eller tensor-rangen.

Notasjon

Kurset bruker notasjon som viser hva slags objekt vi arbeider med:

tall skrives med små bokstaver, for eksempel $x\in\mathbb R$ ;
vektorer skrives med små fete bokstaver, for eksempel $\mathbf a\in\mathbb R^m$ , og $a_i$ er én oppføring;
matriser skrives med store bokstaver, for eksempel $A\in\mathbb R^{m\times n}$ , $a_j$ er kolonne $j$ , og $a_{ij}$ er én oppføring;
tensorer skrives med store fete eller kalligrafiske bokstaver, for eksempel $\mathcal X\in\mathbb R^{m\times n\times p}$ .

Når du skriver for hånd, kan fete symboler markeres med understreking.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 7 · Indeksering av tensorer

Orden, fibre og snitt

En indeks er bare én koordinat i en adresse. For $x_{ij\ell}$ velger $i$ rad, $j$ kolonne og $\ell$ lag. Kolonet : betyr «la denne indeksen variere».

Les alltid indekser fra venstre mot høyre. Plass $1$ , $2$ og $3$ tilhører modus $1$ , $2$ og $3$ - også når noen av plassene inneholder kolon.

Fibre: fest alle unntatt én indeks

For en matrise $A\in\mathbb R^{m\times n}$ er kolonne $j$

a_{:j}\in\mathbb R^m,

fordi $j$ er fast mens radindeksen varierer. Rad $i$ er tilsvarende $a_{i:}\in\mathbb R^n$ .

For $\mathcal X\in\mathbb R^{m\times n\times p}$ kan to indekser festes og én få variere:

x_{:j\ell}\in\mathbb R^m \quad\text{(kolonnefiber, modus 1)},

x_{i:\ell}\in\mathbb R^n \quad\text{(radfiber, modus 2)},

x_{ij:}\in\mathbb R^p \quad\text{(rørfiber, modus 3)}.

Se dette i praksis

La $\mathcal X\in\mathbb R^{2\times2\times2}$ ha frontsnittene

X_{::1}=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \qquad X_{::2}=\begin{pmatrix}5&6\\7&8\end{pmatrix}.

En kolonnefiber med $j=1$ og $\ell=2$ er

x_{:1,2}=\begin{pmatrix}x_{1,1,2}\\x_{2,1,2}\end{pmatrix} =\begin{pmatrix}5\\7\end{pmatrix}.

En radfiber med $i=2$ og $\ell=1$ er

x_{2,:,1}=\begin{pmatrix}3\\4\end{pmatrix}.

En rørfiber med $i=1$ og $j=2$ er

x_{1,2,:}=\begin{pmatrix}2\\6\end{pmatrix}.

I hvert tilfelle varierer akkurat én plass, så resultatet er en vektor.

Hurtigsjekk 38. La

Y_{::1}=\begin{pmatrix}2&4\\6&8\end{pmatrix}, \qquad Y_{::2}=\begin{pmatrix}1&3\\5&7\end{pmatrix}.

Finn $y_{:2,2}$ , $y_{1,:,1}$ og $y_{2,1,:}$ , og angi modusen til hver fiber.

Løsning

Steg 1: I $y_{:2,2}$ varierer første indeks. Vi leser kolonne $2$ i andre frontsnitt:

y_{:2,2}=\begin{pmatrix}3\\7\end{pmatrix},

en modus- $1$ -fiber.

Steg 2: I $y_{1,:,1}$ varierer andre indeks. Første rad i første frontsnitt gir

y_{1,:,1}=\begin{pmatrix}2\\4\end{pmatrix},

en modus- $2$ -fiber.

Steg 3: I $y_{2,1,:}$ varierer tredje indeks. Oppføringen på rad $2$ , kolonne $1$ er $6$ i første lag og $5$ i andre:

y_{2,1,:}=\begin{pmatrix}6\\5\end{pmatrix},

en modus- $3$ -fiber.

Snitt: fest én indeks

Hvis bare én indeks festes i en tredjeordens tensor, varierer to indekser, og resultatet er en matrise:

X_{::\ell}\in\mathbb R^{m\times n}\quad\text{(frontsnitt)},

X_{:j:}\in\mathbb R^{m\times p}\quad\text{(sidesnitt)},

X_{i::}\in\mathbb R^{n\times p}\quad\text{(horisontalsnitt)}.

Se dette i praksis

Bruk tensoren

X_{::1}=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \qquad X_{::2}=\begin{pmatrix}5&6\\7&8\end{pmatrix}.

Når $\ell=1$ er fast, får vi frontsnittet

X_{::1}=\begin{pmatrix}1&2\\3&4\end{pmatrix}.

Når $j=2$ er fast, samler vi kolonne $2$ fra begge lag:

X_{:2:}=\begin{pmatrix}2&6\\4&8\end{pmatrix}.

Når $i=1$ er fast, samler vi første rad fra begge lag:

X_{1::}=\begin{pmatrix}1&5\\2&6\end{pmatrix}.

To kolon betyr at to indekser varierer, så alle tre resultater er matriser.

Hurtigsjekk 39. Bruk tensoren fra hurtigsjekk 38. Finn $Y_{::2}$ , $Y_{:1:}$ og $Y_{2::}$ , og oppgi dimensjonen til hvert snitt.

Løsning

Steg 1: Andre frontsnitt er gitt direkte:

Y_{::2}=\begin{pmatrix}1&3\\5&7\end{pmatrix}\in\mathbb R^{2\times2}.

Steg 2: Kolonne $1$ fra begge lag gir

Y_{:1:}=\begin{pmatrix}2&1\\6&5\end{pmatrix}\in\mathbb R^{2\times2}.

Steg 3: Rad $2$ fra begge lag gir

Y_{2::}=\begin{pmatrix}6&5\\8&7\end{pmatrix}\in\mathbb R^{2\times2}.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 8 · Indre og ytre produkter

Ytre produkter og tensor-rang

Bygg en tensor av tre vektorer

Ett mønster, skalert gjennom snittene

𝓧 = a ∘ b ∘ c

Bruk a = (1, 2), b = (1, −1, 2) og c = (2, −1, 3). Først lager a og b 2 × 3-mønsteret abᵀ. Hver verdi i c, med indeks ℓ, skalerer bare det samme mønsteret.

abᵀ

X_::1 = 2abᵀ

Snitt 1 ganger hver rute i grunnmønsteret med 2. Plasseringene og de proporsjonale radene er de samme; bare størrelsen og, når den valgte c-verdien er negativ, fortegnene endres.

Laster interaktiv modell / Loading interactive model …

Indreprodukt og ytre produkt går i motsatt retning. Indreproduktet kollapser to vektorer til ett tall. Ytreproduktet bygger ut to vektorer til en matrise - og flere vektorer til en tensor.

Klassisk indreprodukt

For $a,b\in\mathbb R^n$ er indreproduktet skalaren

\langle a,b\rangle=a^\top b=\sum_{i=1}^n a_i b_i.

Se dette i praksis

a=\begin{pmatrix}1\\2\\3\end{pmatrix}, \qquad b=\begin{pmatrix}4\\0\\5\end{pmatrix}.

Da er

\langle a,b\rangle =1\cdot4+2\cdot0+3\cdot5 =19.

Svaret er ett tall, ikke en vektor.

Hurtigsjekk 40. Regn ut indreproduktet mellom

u=\begin{pmatrix}2\\-1\\3\end{pmatrix}, \qquad v=\begin{pmatrix}1\\4\\-2\end{pmatrix},

og oppgi typen til resultatet.

Løsning

Steg 1: Gang samsvarende oppføringer og summer:

\langle u,v\rangle=2\cdot1+(-1)\cdot4+3\cdot(-2)=-8.

Steg 2: Resultatet $-8$ er en skalar.

Klassisk ytre produkt

For $u\in\mathbb R^m$ og $v\in\mathbb R^n$ er det ytre produktet matrisen

A=uv^\top\in\mathbb R^{m\times n}, \qquad a_{ij}=u_i v_j.

Hver kolonne er en skalert kopi av $u$ , og hver rad er en skalert kopi av $v^\top$ . Et ikke-null ytre produkt av to ikke-null vektorer har matriserang $1$ .

Se dette i praksis

u=\begin{pmatrix}1\\2\end{pmatrix}, \qquad v=\begin{pmatrix}3\\4\\5\end{pmatrix}.

Da er

uv^\top =\begin{pmatrix}1\\2\end{pmatrix} \begin{pmatrix}3&4&5\end{pmatrix} =\begin{pmatrix}3&4&5\\6&8&10\end{pmatrix}.

Kolonnene er $3u$ , $4u$ og $5u$ . Radene er $v^\top$ og $2v^\top$ . Matrisen har derfor bare én uavhengig rad- og kolonneretning.

Hurtigsjekk 41. La

u=\begin{pmatrix}2\\-1\end{pmatrix}, \qquad v=\begin{pmatrix}4\\0\\3\end{pmatrix}.

Regn ut $uv^\top$ , skriv kolonnene som skalerte kopier av $u$ , og bestem matriserangen.

Løsning

Steg 1: Multipliser hver oppføring i $u$ med hele raden $v^\top$ :

uv^\top =\begin{pmatrix}2\\-1\end{pmatrix} \begin{pmatrix}4&0&3\end{pmatrix} =\begin{pmatrix}8&0&6\\-4&0&-3\end{pmatrix}.

Steg 2: Kolonnene er $4u$ , $0u$ og $3u$ .

Steg 3: Begge faktorene er ikke-null, så matrisen har rang $1$ .

Tensorens ytre produkt

La $a^{(k)}\in\mathbb R^{n_k}$ for $k=1,\ldots,d$ . Det ytre produktet er tensoren

\mathcal X=a^{(1)}\circledcirc a^{(2)}\circledcirc\cdots\circledcirc a^{(d)} \in\mathbb R^{n_1\times\cdots\times n_d},

med oppføringer

x_{i_1,\ldots,i_d} =a^{(1)}_{i_1}a^{(2)}_{i_2}\cdots a^{(d)}_{i_d}.

For $d=2$ er dette det vanlige matriseytreproduktet. For $d=3$ får vi

\mathcal X=a\circledcirc b\circledcirc c, \qquad x_{ij\ell}=a_i b_j c_\ell.

Tensor-rang

En ikke-null tensor $a^{(1)}\circledcirc\cdots\circledcirc a^{(d)}$ har rang $1$ når alle faktorene er ikke-null. Nulltensoren har rang $0$ .

Tensor-rangen til $\mathcal X$ er det minste antallet rang- $1$ -tensorer som trengs for å bygge $\mathcal X$ nøyaktig. Hvis

\mathcal X =\sum_{s=1}^{r}\lambda_s a_s^{(1)}\circledcirc a_s^{(2)}\circledcirc\cdots\circledcirc a_s^{(d)},

har vi vist at $\operatorname{rank}(\mathcal X)\le r$ . Likhet krever i tillegg at færre ledd er umulig.

Se dette i praksis

a=\begin{pmatrix}1\\2\end{pmatrix}, \qquad b=\begin{pmatrix}3\\4\end{pmatrix}, \qquad c=\begin{pmatrix}5\\6\end{pmatrix}.

Tensoren

\mathcal X=a\circledcirc b\circledcirc c

har oppføringer $x_{ij\ell}=a_i b_j c_\ell$ . For eksempel

x_{2,1,2}=a_2b_1c_2=2\cdot3\cdot6=36.

Alle frontsnittene er skalerte kopier av grunnmatrisen $ab^\top$ :

X_{::1}=5ab^\top, \qquad X_{::2}=6ab^\top.

Siden ingen faktor er null, er dette én ikke-null rang- $1$ -tensor.

Hurtigsjekk 42. La

u=\begin{pmatrix}2\\-1\end{pmatrix}, \quad v=\begin{pmatrix}1\\3\end{pmatrix}, \quad w=\begin{pmatrix}4\\2\end{pmatrix}, \qquad \mathcal Y=u\circledcirc v\circledcirc w.

Finn $y_{2,2,1}$ , de to frontsnittene og tensor-rangen.

Løsning

Steg 1: Den valgte oppføringen er

y_{2,2,1}=u_2v_2w_1=(-1)\cdot3\cdot4=-12.

Steg 2: Grunnmatrisen er

uv^\top=\begin{pmatrix}2&6\\-1&-3\end{pmatrix}.

Dermed

Y_{::1}=4uv^\top=\begin{pmatrix}8&24\\-4&-12\end{pmatrix}, \qquad Y_{::2}=2uv^\top=\begin{pmatrix}4&12\\-2&-6\end{pmatrix}.

Steg 3: Alle tre faktorene er ikke-null, så $\operatorname{rank}(\mathcal Y)=1$ .

Praktisk faktormatrisenotasjon

Samle vektorene i samme modus som kolonner:

A^{(k)}= \begin{pmatrix} a_1^{(k)}&a_2^{(k)}&\cdots&a_r^{(k)} \end{pmatrix} \in\mathbb R^{n_k\times r}.

Da kan dekomponeringen skrives

[[\lambda;A^{(1)},\ldots,A^{(d)}]] := \sum_{s=1}^{r}\lambda_s a_s^{(1)}\circledcirc\cdots\circledcirc a_s^{(d)}.

Hvis alle $\lambda_s=1$ , utelates vekten. For $M\in\mathbb R^{m\times n}$ setter den tynne SVD-en $q=\min\{m,n\}$ og bruker $U_q\in\mathbb R^{m\times q}$ og $V_q\in\mathbb R^{n\times q}$ . Da passer SVD-en samme mønster:

M=[[\sigma;U_q,V_q]] =\sum_{s=1}^{q}\sigma_su_sv_s^\top.

For tre modi skriver vi

\mathcal X=[[A,B,C]] =\sum_{s=1}^{r}a_s\circledcirc b_s\circledcirc c_s,

og elementvis

x_{ij\ell}=\sum_{s=1}^{r}a_{is}b_{js}c_{\ell s}.

Se dette i praksis

A=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \quad B=\begin{pmatrix}5&6\\7&8\end{pmatrix}, \quad C=\begin{pmatrix}1&0\\0&1\end{pmatrix}.

Den første kolonnen i hver matrise lager

a_1\circledcirc b_1\circledcirc c_1,

og den andre kolonnen i hver matrise lager

a_2\circledcirc b_2\circledcirc c_2.

Dermed er

\mathcal X=[[A,B,C]] =a_1\circledcirc b_1\circledcirc c_1 +a_2\circledcirc b_2\circledcirc c_2.

For én oppføring får vi

x_{1,2,2} =a_{1,1}b_{2,1}c_{2,1}+a_{1,2}b_{2,2}c_{2,2} =1\cdot7\cdot0+2\cdot8\cdot1=16.

Hurtigsjekk 43. La

A=\begin{pmatrix}1&0\\2&1\end{pmatrix}, \quad B=\begin{pmatrix}2&1\\3&-1\end{pmatrix}, \quad C=\begin{pmatrix}1&2\\0&1\end{pmatrix}, \qquad \mathcal Y=[[A,B,C]].

Skriv de to rang- $1$ -leddene og regn ut $y_{2,1,1}$ .

Løsning

Steg 1: Kolonne $1$ kobles bare til kolonne $1$ , og kolonne $2$ bare til kolonne $2$ :

\mathcal Y=a_1\circledcirc b_1\circledcirc c_1 +a_2\circledcirc b_2\circledcirc c_2.

Steg 2: Bruk elementformelen:

y_{2,1,1} =a_{2,1}b_{1,1}c_{1,1}+a_{2,2}b_{1,2}c_{1,2} =2\cdot2\cdot1+1\cdot1\cdot2=6.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 9 · Matriseoperasjoner

Vektorisering og tre ulike produkter

Samme input, tre ulike regler

Ikke kjenn igjen et produkt bare på symbolet

A, B ∈ ℝ²ˣ²

Hold A = [[1, 2], [3, 4]] og B = [[2, −1], [0, 3]] faste. Bytt bare regel og se hvordan outputformen endres.

A ∗ B

Samme plass møter samme plass

A og B må ha nøyaktig samme form. Gang aᵢⱼ med bᵢⱼ, rute for rute. For eksempel blir 2 · (−1) = −2 øverst til høyre.

Laster interaktiv modell / Loading interactive model …

Vektorisering

Vektorisering lager én lang vektor ved å stable kolonnene i en matrise. For

A=\begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}\in\mathbb R^{m\times n}

definerer vi

\operatorname{vec}(A) =\begin{pmatrix}a_1\\a_2\\\vdots\\a_n\end{pmatrix} \in\mathbb R^{mn}.

Ingen tall endres; bare plasseringen endres.

Se dette i praksis

A=\begin{pmatrix}1&3\\2&4\end{pmatrix}.

Kolonnene er

a_1=\begin{pmatrix}1\\2\end{pmatrix}, \qquad a_2=\begin{pmatrix}3\\4\end{pmatrix}.

Derfor er

\operatorname{vec}(A) =\begin{pmatrix}a_1\\a_2\end{pmatrix} =\begin{pmatrix}1\\2\\3\\4\end{pmatrix}.

Vi leser altså nedover kolonnene, ikke bortover radene.

Hurtigsjekk 44. Vektoriser

P=\begin{pmatrix}2&0&-1\\5&3&4\end{pmatrix}

med kursets konvensjon.

Løsning

Steg 1: Stable første kolonne, deretter andre og tredje:

\operatorname{vec}(P) =\begin{pmatrix}2\\5\\0\\3\\-1\\4\end{pmatrix}.

Steg 2: Matrisen har $2\cdot3=6$ tall, så resultatet ligger i $\mathbb R^6$ .

Kronecker-produkt

For

A=(a_{ij})\in\mathbb R^{m\times n}, \qquad B\in\mathbb R^{p\times q},

er Kronecker-produktet blokkmatrisen

A\otimes B = \begin{pmatrix} a_{11}B&\cdots&a_{1n}B\\ \vdots&\ddots&\vdots\\ a_{m1}B&\cdots&a_{mn}B \end{pmatrix} \in\mathbb R^{mp\times nq}.

For vektorer $a\in\mathbb R^m$ og $b\in\mathbb R^p$ er

a\otimes b =\begin{pmatrix}a_1b\\a_2b\\\vdots\\a_mb\end{pmatrix} \in\mathbb R^{mp}.

Hvis $A=(a_1\ \cdots\ a_n)$ og $B=(b_1\ \cdots\ b_q)$ , kan det samme matriseproduktet skrives kolonnevis som

A\otimes B =\bigl[ a_1\otimes b_1\ \cdots\ a_1\otimes b_q\ \bigm|\ a_2\otimes b_1\ \cdots\ a_2\otimes b_q\ \bigm|\ \cdots\ \bigm|\ a_n\otimes b_1\ \cdots\ a_n\otimes b_q \bigr].

Her kommer altså alle parene $a_j\otimes b_\ell$ med, ordnet med $b$ -indeksen raskest. Dette er forskjellig fra Khatri–Rao-produktet nedenfor, som bare bruker samsvarende kolonnenumre.

Se dette i praksis

A=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \qquad B=\begin{pmatrix}0&5\\6&7\end{pmatrix}.

Da er

A\otimes B =\begin{pmatrix}1B&2B\\3B&4B\end{pmatrix} = \begin{pmatrix} 0&5&0&10\\ 6&7&12&14\\ 0&15&0&20\\ 18&21&24&28 \end{pmatrix}.

For eksempel kommer blokken øverst til høyre fra $a_{12}B=2B$ .

Hurtigsjekk 45. La

C=\begin{pmatrix}1&-1\\2&0\end{pmatrix}, \qquad D=\begin{pmatrix}3&1\\0&2\end{pmatrix}.

Regn ut $C\otimes D$ og oppgi dimensjonen.

Løsning

Steg 1: Erstatt hvert tall i $C$ med en skalert kopi av $D$ :

C\otimes D =\begin{pmatrix}D&-D\\2D&0D\end{pmatrix}.

Steg 2: Gang ut blokkene:

C\otimes D =\begin{pmatrix} 3&1&-3&-1\\ 0&2&0&-2\\ 6&2&0&0\\ 0&4&0&0 \end{pmatrix}.

Begge faktorene er $2\times2$ , så produktet er $4\times4$ .

Khatri–Rao-produkt

A=\begin{pmatrix}a_1&\cdots&a_r\end{pmatrix}\in\mathbb R^{m\times r}, \qquad B=\begin{pmatrix}b_1&\cdots&b_r\end{pmatrix}\in\mathbb R^{p\times r}

ha samme antall kolonner. Khatri–Rao-produktet defineres kolonnevis:

A\odot B =\begin{pmatrix} a_1\otimes b_1& a_2\otimes b_2& \cdots& a_r\otimes b_r \end{pmatrix} \in\mathbb R^{mp\times r}.

Se dette i praksis

A=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \qquad B=\begin{pmatrix}5&6\\7&8\end{pmatrix}.

Første resultatkolonne er

a_1\otimes b_1 =\begin{pmatrix}1\\3\end{pmatrix} \otimes \begin{pmatrix}5\\7\end{pmatrix} =\begin{pmatrix}5\\7\\15\\21\end{pmatrix}.

Andre resultatkolonne er

a_2\otimes b_2 =\begin{pmatrix}2\\4\end{pmatrix} \otimes \begin{pmatrix}6\\8\end{pmatrix} =\begin{pmatrix}12\\16\\24\\32\end{pmatrix}.

Dermed

A\odot B =\begin{pmatrix} 5&12\\ 7&16\\ 15&24\\ 21&32 \end{pmatrix}.

Hurtigsjekk 46. Regn ut $C\odot D$ for

C=\begin{pmatrix}1&-1\\2&3\end{pmatrix}, \qquad D=\begin{pmatrix}4&2\\0&5\end{pmatrix}.

Løsning

Steg 1: Kombiner første kolonne med første kolonne:

c_1\otimes d_1 =\begin{pmatrix}1\\2\end{pmatrix} \otimes \begin{pmatrix}4\\0\end{pmatrix} =\begin{pmatrix}4\\0\\8\\0\end{pmatrix}.

Steg 2: Kombiner andre kolonne med andre kolonne:

c_2\otimes d_2 =\begin{pmatrix}-1\\3\end{pmatrix} \otimes \begin{pmatrix}2\\5\end{pmatrix} =\begin{pmatrix}-2\\-5\\6\\15\end{pmatrix}.

Steg 3: Sett kolonnene sammen:

C\odot D =\begin{pmatrix} 4&-2\\ 0&-5\\ 8&6\\ 0&15 \end{pmatrix}.

Hadamard-produkt

For matriser $A,B\in\mathbb R^{m\times n}$ med samme form er Hadamard-produktet elementvis multiplikasjon:

A\ast B=(a_{ij}b_{ij})\in\mathbb R^{m\times n}.

Se dette i praksis

A=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \qquad B=\begin{pmatrix}10&20\\30&40\end{pmatrix}.

Da er

A\ast B =\begin{pmatrix} 1\cdot10&2\cdot20\\ 3\cdot30&4\cdot40 \end{pmatrix} =\begin{pmatrix}10&40\\90&160\end{pmatrix}.

Formen er fortsatt $2\times2$ .

Hurtigsjekk 47. Regn ut Hadamard-produktet

\begin{pmatrix}2&-1\\0&3\end{pmatrix} \ast \begin{pmatrix}4&5\\7&-2\end{pmatrix}.

Løsning

Steg 1: Gang oppføringer på samme plass:

\begin{pmatrix} 2\cdot4&(-1)\cdot5\\ 0\cdot7&3\cdot(-2) \end{pmatrix} = \begin{pmatrix}8&-5\\0&-6\end{pmatrix}.

Steg 2: Resultatet har samme dimensjon, $2\times2$ .

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 10 · Tensoroperasjoner

Matrisering og $k$ -modusproduktet

Matrisering

Nå kommer vi til delen som virkelig suger, men du må bare komme deg fucking gjennom dette, så blir resten smooth igjen.

Matrisering gjør en tensor om til en matrise uten å endre eller fjerne noen tall. Vi velger én modus som radretning og legger alle fibrene i den modusen som kolonner.

For

\mathcal X\in\mathbb R^{n_1\times\cdots\times n_d}

har modus- $m$ -matriseringen formen

X_{(m)} \in \mathbb R^{n_m\times (n_1\cdots n_{m-1}n_{m+1}\cdots n_d)}.

Kurset bruker første indeks først blant de gjenværende modiene.

Jeg vet at dette ser helt jævlig ut, men la meg bryte det ned: den generelle formelen er bare en oppskrift på hvilket kolonnenummer én tensoroppføring får. For oppføringen $x_{i_1,\ldots,i_d}$ er kolonneadressen i $X_{(m)}$

j =1+\sum_{\substack{k=1\\k\ne m}}^d(i_k-1)j_k, \qquad j_k=\prod_{\substack{\ell<k\\\ell\ne m}}n_\ell.

Her er $j$ det nye kolonnenummeret, mens $j_k$ er spranglengden til indeks $i_k$ . Et tomt produkt er $1$ .

Med andre ord: fjern radindeksen $i_m$ . La den første gjenværende indeksen variere raskest. Tell deretter videre modus for modus.

For $\mathcal X\in\mathbb R^{m\times n\times p}$ gir oppskriften de tre konkrete tilfellene

(X_{(1)})_{i,\,j+(\ell-1)n}=x_{ij\ell},

(X_{(2)})_{j,\,i+(\ell-1)m}=x_{ij\ell},

(X_{(3)})_{\ell,\,i+(j-1)m}=x_{ij\ell}.

Eksempel på matrisering

La $\mathcal X\in\mathbb R^{3\times4\times2}$ ha frontsnittene

X_{::1}= \begin{pmatrix} 1&4&7&10\\ 2&5&8&11\\ 3&6&9&12 \end{pmatrix}, \qquad X_{::2}= \begin{pmatrix} 13&16&19&22\\ 14&17&20&23\\ 15&18&21&24 \end{pmatrix}.

Da blir

X_{(1)}\in\mathbb R^{3\times8}, \qquad X_{(2)}\in\mathbb R^{4\times6}, \qquad X_{(3)}\in\mathbb R^{2\times12}.

Formene kommer før selve omplasseringen: valgt modus gir antallet rader, og produktet av de to andre modusene gir antallet kolonner.

X_{(1)}= \begin{pmatrix} 1&4&7&10&13&16&19&22\\ 2&5&8&11&14&17&20&23\\ 3&6&9&12&15&18&21&24 \end{pmatrix},

X_{(2)}= \begin{pmatrix} 1&2&3&13&14&15\\ 4&5&6&16&17&18\\ 7&8&9&19&20&21\\ 10&11&12&22&23&24 \end{pmatrix},

X_{(3)}= \begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12\\ 13&14&15&16&17&18&19&20&21&22&23&24 \end{pmatrix}.

I $X_{(3)}$ blir hver rørfiber en kolonne. Først varierer radindeksen, deretter kolonneindeksen.

Multilineære transformasjoner

En tensor kan transformeres lineært i hver modus. La

\mathcal X=[[A,B,C]] =\sum_{s=1}^r a_s\circledcirc b_s\circledcirc c_s,

der $A\in\mathbb R^{m\times r}$ , $B\in\mathbb R^{n\times r}$ og $C\in\mathbb R^{p\times r}$ . For

M\in\mathbb R^{m\times u},\qquad N\in\mathbb R^{n\times v},\qquad P\in\mathbb R^{p\times w}

definerer vi

\mathcal X(M,N,P) := \sum_{s=1}^r (M^\top a_s)\circledcirc (N^\top b_s)\circledcirc (P^\top c_s) \in\mathbb R^{u\times v\times w}.

Matrisene er skrevet med denne retningen fordi $M^\top$ sender en $m$ -vektor til en $u$ -vektor, $N^\top$ sender $n$ til $v$ , og $P^\top$ sender $p$ til $w$ .

Det samme kan skrives

\mathcal X(M,N,P) =[[M^\top A,N^\top B,P^\top C]].

Se dette i praksis

Start med rang- $1$ -tensoren

\mathcal X=a\circledcirc b\circledcirc c, \qquad a=\begin{pmatrix}1\\2\end{pmatrix}, \quad b=\begin{pmatrix}3\\4\end{pmatrix}, \quad c=\begin{pmatrix}5\\6\end{pmatrix}.

Velg

M=\begin{pmatrix}1\\1\end{pmatrix}, \qquad N=\begin{pmatrix}1\\0\end{pmatrix}, \qquad P=\begin{pmatrix}0\\1\end{pmatrix}.

Hver modus kollapser til ett indreprodukt:

M^\top a=3,\qquad N^\top b=3,\qquad P^\top c=6.

Den transformerte tensoren har form $1\times1\times1$ , altså bare tallet

\mathcal X(M,N,P)=3\cdot3\cdot6=54.

Hurtigsjekk 48. La $\mathcal Y=u\circledcirc v\circledcirc w$ med

u=\begin{pmatrix}2\\-1\end{pmatrix},\quad v=\begin{pmatrix}1\\3\end{pmatrix},\quad w=\begin{pmatrix}4\\2\end{pmatrix}.

Bruk

M=\begin{pmatrix}1\\2\end{pmatrix}, \qquad N=\begin{pmatrix}2\\-1\end{pmatrix}, \qquad P=\begin{pmatrix}1\\1\end{pmatrix}.

Finn $\mathcal Y(M,N,P)$ .

Løsning

Steg 1: Regn ett indreprodukt i hver modus:

M^\top u=1\cdot2+2(-1)=0,

N^\top v=2\cdot1+(-1)3=-1, \qquad P^\top w=4+2=6.

Steg 2: Multipliser de tre skalarene:

\mathcal Y(M,N,P)=0\cdot(-1)\cdot6=0.

Matriseeksempel

For $A\in\mathbb R^{m\times r}$ og $B\in\mathbb R^{n\times r}$ er

[[A,B]]=AB^\top.

Transformasjon i første modus gir $M^\top A$ , transformasjon i andre gir $N^\top B$ , og samlet

[[A,B]](M,N)=M^\top AB^\top N.

Kollapseringseksempel

Hvis én ny dimensjon er $1$ , forsvinner denne modusen som egen akse. For $P\in\mathbb R^{p\times1}$ er

P^\top c_s=\langle P,c_s\rangle

en skalar. Produktet har da én modus mindre.

$k$ -modusproduktet

Pust. $\times_k$ er ikke en ny mystisk type multiplikasjon; det er vanlig matrisemultiplikasjon brukt langs én valgt tensorretning.

\mathcal X\in\mathbb R^{n_1\times\cdots\times n_d}, \qquad Q\in\mathbb R^{q\times n_k}.

$k$ -modusproduktet

\mathcal Y=\mathcal X\times_kQ \in \mathbb R^{n_1\times\cdots\times n_{k-1}\times q\times n_{k+1}\times\cdots\times n_d}

har oppføringer

y_{i_1,\ldots,i_{k-1},j,i_{k+1},\ldots,i_d} = \sum_{i_k=1}^{n_k} x_{i_1,\ldots,i_d}q_{j,i_k}.

I matrisert form blir hele regelen vanlig matrisemultiplikasjon:

Y_{(k)}=QX_{(k)}.

Se dette i praksis

Se matrisen

B=\begin{pmatrix}1&2\\3&4\end{pmatrix}

som en tensor av orden $2$ .

I modus $1$ , med

A=\begin{pmatrix}2&0\\0&1\end{pmatrix},

får vi

B\times_1A=AB =\begin{pmatrix}2&4\\3&4\end{pmatrix}.

Første radretning dobles, mens den andre beholdes.

I modus $2$ , med

C=\begin{pmatrix}1&0\\0&3\end{pmatrix},

får vi

B\times_2C=BC^\top =\begin{pmatrix}1&6\\3&12\end{pmatrix}.

Første kolonneretning beholdes, mens den andre tredobles.

Hurtigsjekk 49. La

D=\begin{pmatrix}1&0\\2&3\end{pmatrix},\quad P=\begin{pmatrix}3&0\\0&1\end{pmatrix},\quad Q=\begin{pmatrix}1&0\\0&2\end{pmatrix}.

Finn $D\times_1P$ og $D\times_2Q$ .

Løsning

Steg 1: Modus $1$ betyr venstremultiplikasjon:

D\times_1P=PD =\begin{pmatrix}3&0\\2&3\end{pmatrix}.

Steg 2: Modus $2$ betyr multiplikasjon med transponert transformasjon på høyre side:

D\times_2Q=DQ^\top =\begin{pmatrix}1&0\\2&6\end{pmatrix}.

Matrisetilfellene

En matrise har bare to modi. For $B\in\mathbb R^{m\times n}$ kan vi derfor lese reglene som to kjente matriseprodukter.

I modus $1$ transformeres radretningen:

B\times_1Q=QB \quad\text{for }Q\in\mathbb R^{q\times m}.

I modus $2$ transformeres kolonneretningen:

B\times_2Q=BQ^\top \quad\text{for }Q\in\mathbb R^{q\times n}.

Vektortilfellet av $k$ -modusproduktet

Når vi kontraherer med en vektor $a\in\mathbb R^{n_k}$ , tolkes den som radtransformasjonen $a^\top\in\mathbb R^{1\times n_k}$ . Modusen summeres bort, og tensorordenen synker med én:

\mathcal Z=\mathcal X\times_ka,

z_{i_1,\ldots,i_{k-1},i_{k+1},\ldots,i_d} = \sum_{i_k=1}^{n_k} x_{i_1,\ldots,i_d}a_{i_k}.

For en matrise er

B\times_1v=B^\top v, \qquad B\times_2w=Bw.

Se dette i praksis

B=\begin{pmatrix}1&2\\3&4\end{pmatrix}.

Kontraher modus $1$ med

v=\begin{pmatrix}10\\1\end{pmatrix}.

Da får vi

B\times_1v =B^\top v =\begin{pmatrix}1&3\\2&4\end{pmatrix} \begin{pmatrix}10\\1\end{pmatrix} =\begin{pmatrix}13\\24\end{pmatrix}.

Kontraher i stedet modus $2$ med

w=\begin{pmatrix}1\\10\end{pmatrix}.

Da får vi

B\times_2w =Bw =\begin{pmatrix}1&2\\3&4\end{pmatrix} \begin{pmatrix}1\\10\end{pmatrix} =\begin{pmatrix}21\\43\end{pmatrix}.

En matrise av orden $2$ er blitt en vektor av orden $1$ .

Hurtigsjekk 50. For

D=\begin{pmatrix}2&1\\-1&3\end{pmatrix}, \quad v=\begin{pmatrix}2\\4\end{pmatrix}, \quad w=\begin{pmatrix}3\\-1\end{pmatrix},

finn $D\times_1v$ og $D\times_2w$ .

Løsning

Steg 1: Kontraksjon i første modus gir

D^\top v =\begin{pmatrix}2&-1\\1&3\end{pmatrix} \begin{pmatrix}2\\4\end{pmatrix} =\begin{pmatrix}0\\14\end{pmatrix}.

Steg 2: Kontraksjon i andre modus gir

Dw =\begin{pmatrix}2&1\\-1&3\end{pmatrix} \begin{pmatrix}3\\-1\end{pmatrix} =\begin{pmatrix}5\\-6\end{pmatrix}.

Khatri–Rao-produkt og matrisering

Hvis

\mathcal X=[[A,B,C]] \in\mathbb R^{m\times n\times p},

er de tre viktige identitetene

X_{(1)}=A(C\odot B)^\top,

X_{(2)}=B(C\odot A)^\top,

X_{(3)}=C(B\odot A)^\top.

Rekkefølgen følger kursets første-indeks-først-konvensjon. For ett rang- $1$ -ledd blir for eksempel kolonnen med de andre faktorene $c\otimes b$ , ikke $b\otimes c$ .

Se dette i praksis

A=\begin{pmatrix}1&2\\3&4\end{pmatrix}, \quad B=\begin{pmatrix}1&0\\0&1\end{pmatrix}, \quad C=\begin{pmatrix}2&1\\1&3\end{pmatrix}.

De samsvarende Kronecker-kolonnene er

c_1\otimes b_1 =\begin{pmatrix}2\\0\\1\\0\end{pmatrix}, \qquad c_2\otimes b_2 =\begin{pmatrix}0\\1\\0\\3\end{pmatrix}.

Derfor

C\odot B =\begin{pmatrix} 2&0\\ 0&1\\ 1&0\\ 0&3 \end{pmatrix}.

Nå blir tensoruttrykket en vanlig matriseproduktberegning:

X_{(1)} =A(C\odot B)^\top = \begin{pmatrix} 2&2&1&6\\ 6&4&3&12 \end{pmatrix}.

Hurtigsjekk 51. La

A=\begin{pmatrix}1&0\\2&1\end{pmatrix},\quad B=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad C=\begin{pmatrix}1&2\\3&1\end{pmatrix}.

Finn $C\odot B$ og deretter $X_{(1)}=A(C\odot B)^\top$ .

Løsning

Steg 1: Beregn de samsvarende Kronecker-kolonnene:

c_1\otimes b_1 =\begin{pmatrix}1\\0\\3\\0\end{pmatrix}, \qquad c_2\otimes b_2 =\begin{pmatrix}0\\2\\0\\1\end{pmatrix}.

Dermed

C\odot B =\begin{pmatrix} 1&0\\ 0&2\\ 3&0\\ 0&1 \end{pmatrix}.

Steg 2: Multipliser:

X_{(1)} =\begin{pmatrix}1&0\\2&1\end{pmatrix} \begin{pmatrix} 1&0&3&0\\ 0&2&0&1 \end{pmatrix} = \begin{pmatrix} 1&0&3&0\\ 2&2&6&1 \end{pmatrix}.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 11 · Tensordekomponering: CP og ALS

CP-dekomponering og ALS

Canonical Polyadic (CP) + alternerende minste kvadrater (ALS)

To enkle lag kan forklare ett rikere mønster

X ≈ Σᵣ aᵣ ∘ bᵣ ∘ cᵣ

Under tilnærmes ett vist snitt av X med to rang-1-komponentsnitt. Velg en komponent for å se jobben dens.

a₁ ∘ b₁ ∘ c₁

a₂ ∘ b₂ ∘ c₂

X̂_::1

X̂ = layer 1 + layer 2

CP bygger en komplisert tensor ved å summere et lite antall enkle rang-1-komponenter.

Alternerende minste kvadrater

Oppdater én faktor, frys de to andre

Hold B og C faste. Finn A som passer X best med minste kvadrater.

Laster interaktiv modell / Loading interactive model …

CP står for Canonical Polyadic og er selve dekomponeringsmodellen. ALS står for Alternating Least Squares og er algoritmen vi bruker for å tilpasse modellen til dataene.

Motivasjon fra SVD

For $M\in\mathbb R^{m\times n}$ setter vi $q=\min\{m,n\}$ og bruker de tynne SVD-faktorene $U_q\in\mathbb R^{m\times q}$ og $V_q\in\mathbb R^{n\times q}$ . Da skriver SVD matrisen som en sum av rang- $1$ -matriser:

M=U_q\Sigma_qV_q^\top =\sum_{s=1}^{q}\sigma_su_sv_s^\top =[[\,\sigma;U_q,V_q\,]].

Tensoranalogen spør om en komplisert tensor kan bygges eller tilnærmes med noen få enkle ytre-produkt-blokker:

\mathcal X \approx \sum_{s=1}^{r}a_s\circledcirc b_s\circledcirc c_s =[[A,B,C]].

Flere blokker gir vanligvis en bedre tilnærming, men hver enkelt blokk er fortsatt rang $1$ .

Se dette i praksis

Ta to rang- $1$ -ledd:

a_1=\begin{pmatrix}1\\2\end{pmatrix},\quad b_1=\begin{pmatrix}1\\0\end{pmatrix},\quad c_1=\begin{pmatrix}1\\3\end{pmatrix},

a_2=\begin{pmatrix}0\\1\end{pmatrix},\quad b_2=\begin{pmatrix}2\\1\end{pmatrix},\quad c_2=\begin{pmatrix}1\\1\end{pmatrix}.

Det første leddet har grunnmatrise

a_1b_1^\top=\begin{pmatrix}1&0\\2&0\end{pmatrix}

og frontsnitt

X^{(1)}_{::1}=\begin{pmatrix}1&0\\2&0\end{pmatrix}, \qquad X^{(1)}_{::2}=\begin{pmatrix}3&0\\6&0\end{pmatrix}.

Det andre leddet har grunnmatrise

a_2b_2^\top=\begin{pmatrix}0&0\\2&1\end{pmatrix}

og samme bidrag i begge lag. Når leddene legges sammen, blir

X_{::1}\approx\begin{pmatrix}1&0\\4&1\end{pmatrix}, \qquad X_{::2}\approx\begin{pmatrix}3&0\\8&1\end{pmatrix}.

Et rikere mønster er blitt bygget av to enkle blokker.

Hurtigsjekk 52. La

a_1=\begin{pmatrix}1\\1\end{pmatrix},\qquad b_1=\begin{pmatrix}2\\0\end{pmatrix},\qquad c_1=\begin{pmatrix}1\\2\end{pmatrix},

a_2=\begin{pmatrix}1\\-1\end{pmatrix},\qquad b_2=\begin{pmatrix}0\\1\end{pmatrix},\qquad c_2=\begin{pmatrix}3\\1\end{pmatrix}.

Finn de to frontsnittene til summen av de to rang- $1$ -leddene.

Løsning

Steg 1: Grunnmatrisene er

a_1b_1^\top=\begin{pmatrix}2&0\\2&0\end{pmatrix}, \qquad a_2b_2^\top=\begin{pmatrix}0&1\\0&-1\end{pmatrix}.

Steg 2: Første lag bruker vektene $1$ og $3$ :

X_{::1} =a_1b_1^\top+3a_2b_2^\top =\begin{pmatrix}2&3\\2&-3\end{pmatrix}.

Steg 3: Andre lag bruker vektene $2$ og $1$ :

X_{::2} =2a_1b_1^\top+a_2b_2^\top =\begin{pmatrix}4&1\\4&-1\end{pmatrix}.

Canonical Polyadic-dekomponering

Tensorens Frobenius-norm er

\|\mathcal X\|_F = \sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{\ell=1}^{p}x_{ij\ell}^2}.

Canonical Polyadic-dekomponering av en tredjeordens tensor

La $\mathcal X\in\mathbb R^{m\times n\times p}$ . En eksakt CP-dekomponering med $r$ ledd er

\mathcal X =\sum_{s=1}^{r}a_s\circledcirc b_s\circledcirc c_s =[[A,B,C]],

der

A\in\mathbb R^{m\times r},\qquad B\in\mathbb R^{n\times r},\qquad C\in\mathbb R^{p\times r}.

Det minste $r$ som gjør en slik likhet mulig, er CP-rangen. Med et fast antall $r$ ledd finner en CP-tilnærming faktorer som løser

\min_{\substack{ A\in\mathbb R^{m\times r},\, B\in\mathbb R^{n\times r},\, C\in\mathbb R^{p\times r}}} \left\| \mathcal X- \sum_{s=1}^{r}a_s\circledcirc b_s\circledcirc c_s \right\|_F^2.

Hvis feilen er null, har vi en eksakt representasjon med høyst $r$ ledd. Hvis feilen er positiv, har vi en $r$ -ledds CP-tilnærming, ikke et bevis på at tensor-rangen er $r$ .

Canonical Polyadic forkortes CP. Navnene CANDECOMP og PARAFAC brukes også. Et eksplisitt vekttall $\lambda_s$ kan absorberes i én av faktorvektorene.

Se dette i praksis

La en tensor ha snittene

X_{::1}=\begin{pmatrix}1&0\\0&1\end{pmatrix}, \qquad X_{::2}=\begin{pmatrix}2&0\\0&2\end{pmatrix}.

En rang- $1$ -modell

\mathcal Y=a\circledcirc b\circledcirc c

må ha snitt som skalerte kopier av den samme rang- $1$ -matrisen $ab^\top$ . Velger vi

a=b=\begin{pmatrix}1\\0\end{pmatrix}, \qquad c=\begin{pmatrix}1\\2\end{pmatrix},

får vi

Y_{::1}=\begin{pmatrix}1&0\\0&0\end{pmatrix}, \qquad Y_{::2}=\begin{pmatrix}2&0\\0&0\end{pmatrix}.

Den øvre venstre strukturen treffes, men den nedre høyre mangler. Legger vi til

\begin{pmatrix}0\\1\end{pmatrix} \circledcirc \begin{pmatrix}0\\1\end{pmatrix} \circledcirc \begin{pmatrix}1\\2\end{pmatrix},

rekonstrueres begge snittene nøyaktig med to rang- $1$ -ledd.

Hurtigsjekk 53. En tensor har snittene

Z_{::1}=\begin{pmatrix}2&0\\0&3\end{pmatrix}, \qquad Z_{::2}=\begin{pmatrix}-1&0\\0&6\end{pmatrix}.

Finn en eksakt CP-dekomponering med to ledd, og forklar hvorfor ett ledd ikke er nok.

Løsning

Steg 1: Del de to diagonalretningene:

\mathcal Z =e_1\circledcirc e_1\circledcirc \begin{pmatrix}2\\-1\end{pmatrix} + e_2\circledcirc e_2\circledcirc \begin{pmatrix}3\\6\end{pmatrix}.

Dette gir nøyaktig de oppgitte diagonalene i begge lag.

Steg 2: Allerede $Z_{::1}$ har matriserang $2$ . Et enkelt tensorytreprodukt ville gitt et snitt som er en skalert rang- $1$ -matrise. Ett ledd er derfor umulig, og CP-rangen er $2$ .

Beregning av CP-dekomponering med alternerende minste kvadrater

Direkte minimering er vanskelig fordi $A$ , $B$ og $C$ påvirker hverandre. Alternating Least Squares (ALS) fryser to faktormatriser og oppdaterer den tredje.

Ikke la de tre linjene nedenfor skremme deg: hver linje er bare et vanlig minste-kvadraters problem der to faktorer holdes fast og én får bevege seg.

Fra matriseringene får vi tre vanlige minste-kvadraters problemer:

Her er hevet $+$ bare en merkelapp for den nyoppdaterte faktoren. Moore–Penrose-pseudoinversen som brukes i løsningene nedenfor, skrives $\dagger$ .

Oppdater $A$ . Hold $B$ og $C$ fast, og la bare $A$ bevege seg:

A^+ = \arg\min_{\widetilde A} \|X_{(1)}-\widetilde A(C\odot B)^\top\|_F^2,

Oppdater $B$ . Bruk den nye $A^+$ , hold $C$ fast, og la $B$ bevege seg:

B^+ = \arg\min_{\widetilde B} \|X_{(2)}-\widetilde B(C\odot A^+)^\top\|_F^2,

Oppdater $C$ . Bruk de nye $A^+$ og $B^+$ , og la til slutt $C$ bevege seg:

C^+ = \arg\min_{\widetilde C} \|X_{(3)}-\widetilde C(B^+\odot A^+)^\top\|_F^2.

Pseudoinversen gir praktiske oppdateringer:

A^+=X_{(1)}\bigl((C\odot B)^\top\bigr)^\dagger,

B^+=X_{(2)}\bigl((C\odot A^+)^\top\bigr)^\dagger,

C^+=X_{(3)}\bigl((B^+\odot A^+)^\top\bigr)^\dagger.

Se dette i praksis

Se først på matriseanalogen

X\approx ab^\top.

X=\begin{pmatrix}2&4\\3&6\end{pmatrix}, \qquad b=\begin{pmatrix}1\\2\end{pmatrix}.

Når $b$ holdes fast, velger vi $a$ slik at

ab^\top = \begin{pmatrix}a_1\\a_2\end{pmatrix} \begin{pmatrix}1&2\end{pmatrix} = \begin{pmatrix} a_1&2a_1\\ a_2&2a_2 \end{pmatrix}

passer $X$ . Her ser vi direkte at

a=\begin{pmatrix}2\\3\end{pmatrix},

og da er $ab^\top=X$ . Tensor-ALS gjør den samme typen tilpasning, men veksler mellom $A$ , $B$ og $C$ .

Hurtigsjekk 54. La

Y=\begin{pmatrix}3&-6\\1&-2\end{pmatrix}, \qquad b=\begin{pmatrix}1\\-2\end{pmatrix}.

Hold $b$ fast og finn $a$ slik at $Y=ab^\top$ .

Løsning

Steg 1: Skriv modellen:

ab^\top = \begin{pmatrix}a_1\\a_2\end{pmatrix} \begin{pmatrix}1&-2\end{pmatrix} = \begin{pmatrix}a_1&-2a_1\\a_2&-2a_2\end{pmatrix}.

Steg 2: Sammenlign første kolonne med $Y$ . Da får vi

a=\begin{pmatrix}3\\1\end{pmatrix}.

Den andre kolonnen blir automatisk

\begin{pmatrix}-6\\-2\end{pmatrix},

så modellen er eksakt.

ALS-algoritmen

Velg modellstørrelse $r$ og startmatriser $A^{(0)},B^{(0)},C^{(0)}$ . For $k=0,1,\ldots$ gjør vi

A^{(k+1)} =X_{(1)} \left((C^{(k)}\odot B^{(k)})^\top\right)^\dagger,

B^{(k+1)} =X_{(2)} \left((C^{(k)}\odot A^{(k+1)})^\top\right)^\dagger,

C^{(k+1)} =X_{(3)} \left((B^{(k+1)}\odot A^{(k+1)})^\top\right)^\dagger.

Deretter bygges $\widehat{\mathcal X}^{(k+1)}$ og for eksempel den relative feilen

\rho_{k+1} = \frac{\|\mathcal X-\widehat{\mathcal X}^{(k+1)}\|_F} {\|\mathcal X\|_F}

kontrolleres. Stopp når feilen er liten nok, nesten ikke endres, eller et maksimalt antall iterasjoner er nådd.

Se dette i praksis

Velg en CP-modell med $r=2$ ledd. Da har faktorene form

A\in\mathbb R^{m\times2},\qquad B\in\mathbb R^{n\times2},\qquad C\in\mathbb R^{p\times2}.

Én iterasjon ser slik ut:

Start med $A^{(0)},B^{(0)},C^{(0)}$ .
Frys $B^{(0)}$ og $C^{(0)}$ , og finn en bedre $A^{(1)}$ .
Bruk den nye $A^{(1)}$ , frys den og $C^{(0)}$ , og finn $B^{(1)}$ .
Bruk både $A^{(1)}$ og $B^{(1)}$ , og finn $C^{(1)}$ .
Bruk $A^{(1)},B^{(1)},C^{(1)}$ som start for neste runde.

Tallet i parentes er iterasjonsnummeret; det er ikke en potens.

Hurtigsjekk 55. For $\mathcal X\in\mathbb R^{4\times3\times2}$ brukes en CP-modell med $r=2$ ledd. Oppgi dimensjonene til $A,B,C$ , og fortell hvilke gamle eller nye faktorer som brukes i hver av de tre oppdateringene fra iterasjon $k$ til $k+1$ .

Løsning

Steg 1: Faktordimensjonene er

A:4\times2,\qquad B:3\times2,\qquad C:2\times2.

Steg 2: $A^{(k+1)}$ bruker gamle $B^{(k)}$ og $C^{(k)}$ .

Steg 3: $B^{(k+1)}$ bruker nye $A^{(k+1)}$ og gamle $C^{(k)}$ .

Steg 4: $C^{(k+1)}$ bruker både nye $A^{(k+1)}$ og nye $B^{(k+1)}$ . Først da er én hel ALS-syklus ferdig.

Følg en hel numerisk ALS-syklus

Vi bruker rang $r=1$ og måltensoren

\mathcal X=a_*\circledcirc b_*\circledcirc c_*, \quad a_*=\begin{pmatrix}1\\2\end{pmatrix},\qquad b_*=\begin{pmatrix}1\\3\end{pmatrix},\qquad c_*=\begin{pmatrix}2\\-1\end{pmatrix}.

Frontsnittene er

X_{::1}=\begin{pmatrix}2&6\\4&12\end{pmatrix}, \qquad X_{::2}=\begin{pmatrix}-1&-3\\-2&-6\end{pmatrix},

og matriseringene er

X_{(1)}=\begin{pmatrix}2&6&-1&-3\\4&12&-2&-6\end{pmatrix},

X_{(2)}=\begin{pmatrix}2&4&-1&-2\\6&12&-3&-6\end{pmatrix}, \qquad X_{(3)}=\begin{pmatrix}2&4&6&12\\-1&-2&-3&-6\end{pmatrix}.

Start med

b^{(0)}=\begin{pmatrix}1\\1\end{pmatrix}, \qquad c^{(0)}=\begin{pmatrix}1\\0\end{pmatrix}.

For rang $1$ har problemet $\min_z\|X-zk^\top\|_F^2$ løsningen $z=Xk/(k^\top k)$ .

Først

k_A=c^{(0)}\otimes b^{(0)} =\begin{pmatrix}1\\1\\0\\0\end{pmatrix}, \qquad a^{(1)} =\frac{X_{(1)}k_A}{k_A^\top k_A} =\begin{pmatrix}4\\8\end{pmatrix}.

Deretter

k_B=c^{(0)}\otimes a^{(1)} =\begin{pmatrix}4\\8\\0\\0\end{pmatrix}, \qquad b^{(1)} =\frac{X_{(2)}k_B}{k_B^\top k_B} =\begin{pmatrix}1/2\\3/2\end{pmatrix}.

Til slutt

k_C=b^{(1)}\otimes a^{(1)} =\begin{pmatrix}2\\4\\6\\12\end{pmatrix}, \qquad c^{(1)} =\frac{X_{(3)}k_C}{k_C^\top k_C} =\begin{pmatrix}1\\-1/2\end{pmatrix}.

Faktorene oppfyller

a^{(1)}=4a_*, \qquad b^{(1)}=\tfrac12b_*, \qquad c^{(1)}=\tfrac12c_*.

Skalaene ganger seg til $1$ , så rekonstruksjonen er nøyaktig. Siden

\|\mathcal X\|_F =\sqrt{2^2+6^2+4^2+12^2+(-1)^2+(-3)^2+(-2)^2+(-6)^2} =\sqrt{250},

blir den eksplisitte kontrollen

\rho_1=\frac{0}{\sqrt{250}}=0.

I generelle data må syklusen gjentas.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

Del 12 · Tucker-dekomponering, HOSVD og HOOI

Tucker, HOSVD og HOOI

Tucker-dekomponering + høyereordens singularverdidekomponering (HOSVD)

En liten kjerne pluss tre retningsordbøker

X ≈ X̂ = G ×₁ A ×₂ B ×₃ C

Tenk på A, B og C som ordbøker: hver kolonne er et gjenbrukbart retningsmønster. Den lille kjernen G lagrer hvilke mønsterkombinasjoner som betyr noe, og hvor sterkt de skal blandes.

Hele datasettet

X · 4 × 3 × 3

Kombinasjonstabell

G · 2 × 2 × 2

×₁ AA ∈ ℝ^4×2

×₂ BB ∈ ℝ^3×2

×₃ CC ∈ ℝ^3×2

Rekonstruksjon

X̂ · 4 × 3 × 3

G ∈ ℝ²ˣ²ˣ²

Start med den lille 2 × 2 × 2-kjernen. Den er en kombinasjonstabell, ikke et miniatyrbilde: g[p,q,r] sier hvor sterkt retning p fra A, retning q fra B og retning r fra C skal virke sammen.

Algoritmevisualisering

Slik finner høyereordens singularverdidekomponering A, B, C og G

Matrisér → SVD → behold retninger → komprimer

X · 4 × 3 × 3

X₍₁₎ · 4 × 9

×₁ AA ∈ ℝ^4×2

X₍₁₎ ∈ ℝ^4×9 → A ∈ ℝ^4×2

Legg alle modus-1-fibrene som kolonner i modus-1-matriseringen. Beregn singularverdidekomponeringen og behold de to ledende venstre singularvektorene. De blir de to kolonnene i A.

Laster interaktiv modell / Loading interactive model …

Motivasjon fra SVD og modusprodukter

Tucker ser først ut som CP med altfor mange bevegelige deler, men hovedideen er enkel: en liten kjerne forteller hvilke retninger som får lov til å blandes.

SVD kan skrives med modusprodukter:

M=U\Sigma V^\top =\Sigma\times_1U\times_2V.

Her er $\Sigma$ en liten, diagonal kjerne, mens $U$ og $V$ utvider kjernen i hver sin retning. For en tredjeordens tensor bruker Tucker samme idé med en kjerne og tre faktormatriser:

\mathcal G\in\mathbb R^{r_1\times r_2\times r_3},

A\in\mathbb R^{m\times r_1},\qquad B\in\mathbb R^{n\times r_2},\qquad C\in\mathbb R^{p\times r_3},

\mathcal Y =\mathcal G\times_1A\times_2B\times_3C.

Utvidet som ytre produkter er dette

\mathcal Y = \sum_{\alpha=1}^{r_1} \sum_{\beta=1}^{r_2} \sum_{\gamma=1}^{r_3} g_{\alpha\beta\gamma} a_\alpha\circledcirc b_\beta\circledcirc c_\gamma.

Hvis $r_1=r_2=r_3=r$ og kjernen er superdiagonal,

g_{\alpha\beta\gamma} = \begin{cases} \lambda_\alpha,&\alpha=\beta=\gamma,\\ 0,&\text{ellers}, \end{cases}

står bare samsvarende tripler igjen. Da er CP et spesialtilfelle av Tucker.

Se dette i praksis

I en CP-modell med to ledd får vi bare de samsvarende triplene

a_1\circledcirc b_1\circledcirc c_1 + a_2\circledcirc b_2\circledcirc c_2.

En Tucker-kjerne kan også blande forskjellige kolonnenumre. La

\mathcal G\in\mathbb R^{2\times2\times2}

ha bare to ikke-null oppføringer:

g_{1,1,1}=5, \qquad g_{2,1,2}=3.

Da er

\mathcal Y =5a_1\circledcirc b_1\circledcirc c_1 +3a_2\circledcirc b_1\circledcirc c_2.

Det andre leddet kobler retning $2$ fra $A$ , retning $1$ fra $B$ og retning $2$ fra $C$ . Kjernen tillater altså krysskoblinger som en superdiagonal CP-kjerne ikke tillater.

Hurtigsjekk 56. En $2\times2\times2$ -kjerne har bare $g_{1,2,1}=-2$ og $g_{2,1,2}=4$ som ikke-null oppføringer. Skriv Tucker-modellen som en sum av to ytre produkter, og forklar hvorfor dette ikke er en CP-kjerne i den oppgitte basisen.

Løsning

Steg 1: Hver ikke-null kjerneoppføring velger én kolonne fra hver faktor:

\mathcal Y =-2a_1\circledcirc b_2\circledcirc c_1 +4a_2\circledcirc b_1\circledcirc c_2.

Steg 2: En CP-kjerne er superdiagonal og kobler bare $(1,1,1)$ , $(2,2,2)$ og så videre. Her brukes $(1,2,1)$ og $(2,1,2)$ , så kjernen har krysskoblinger.

Definisjon av Tucker-dekomponering

Tucker-dekomponering av en tredjeordens tensor

For $\mathcal X\in\mathbb R^{m\times n\times p}$ og valgte størrelser $(r_1,r_2,r_3)$ finner en Tucker-tilnærming

\min_{\substack{ \mathcal G\in\mathbb R^{r_1\times r_2\times r_3},\, A\in\mathbb R^{m\times r_1}\\ B\in\mathbb R^{n\times r_2},\, C\in\mathbb R^{p\times r_3}}} \left\| \mathcal X- \mathcal G\times_1A\times_2B\times_3C \right\|_F^2,

der

\mathcal G\in\mathbb R^{r_1\times r_2\times r_3}, \quad A\in\mathbb R^{m\times r_1}, \quad B\in\mathbb R^{n\times r_2}, \quad C\in\mathbb R^{p\times r_3}.

Modelltensoren er

\mathcal Y =\mathcal G\times_1A\times_2B\times_3C,

og elementvis

y_{ij\ell} = \sum_{\alpha=1}^{r_1} \sum_{\beta=1}^{r_2} \sum_{\gamma=1}^{r_3} g_{\alpha\beta\gamma} a_{i\alpha}b_{j\beta}c_{\ell\gamma}.

Les formelen fra høyre: $a_{i\alpha}$ sier hvor mye kjerneretning $\alpha$ bidrar på plass $i$ i modus $1$ . Tilsvarende gjør $b_{j\beta}$ og $c_{\ell\gamma}$ jobben i modus $2$ og $3$ . Tallet $g_{\alpha\beta\gamma}$ bestemmer hvor sterkt akkurat denne kombinasjonen av tre retninger skal brukes.

For en tredjeordens tensor $\mathcal Z$ er multirangen tuplet

\bigl(\operatorname{rank}(Z_{(1)}), \operatorname{rank}(Z_{(2)}), \operatorname{rank}(Z_{(3)})\bigr).

Modelltensoren $\mathcal Y$ har derfor multirang som komponentvis er høyst $(r_1,r_2,r_3)$ ; den faktiske multirangen til modellen kan være mindre.

Visste du at?

Eksamenssnarvei: Tucker-former og lagring.

Se etter: Startformen $m\times n\times p$ og målstørrelsene $(r_1,r_2,r_3)$ .
Raskeste vei: Skriv $\mathcal G:r_1\times r_2\times r_3$ , $A:m\times r_1$ , $B:n\times r_2$ og $C:p\times r_3$ . Sammenlign deretter $mnp$ tall med

r_1r_2r_3+mr_1+nr_2+pr_3.

Vanlig felle: $(r_1,r_2,r_3)$ er tre modus-størrelser, ikke én CP-rang. De begrenser multirangen til modellen $\mathcal Y$ ; de trenger ikke være den eksakte multirangen til $\mathcal X$ .
Kontroll: Etter alle tre modusproduktene må rekonstruksjonen igjen ha form $m\times n\times p$ .

Se dette i praksis

Anta at den opprinnelige tensoren er

\mathcal X\in\mathbb R^{100\times80\times50},

og velg Tucker-størrelser

r_1=5,\qquad r_2=4,\qquad r_3=3.

Da har kjernen og faktorene dimensjonene

\mathcal G\in\mathbb R^{5\times4\times3},

A\in\mathbb R^{100\times5},\qquad B\in\mathbb R^{80\times4},\qquad C\in\mathbb R^{50\times3}.

Modellen

\mathcal X\approx \mathcal G\times_1A\times_2B\times_3C

lagrer en liten kjerne og tre smale faktormatriser. Den fulle tensoren krever

100\cdot80\cdot50=400\,000

tall. Tucker-formen krever

5\cdot4\cdot3+100\cdot5+80\cdot4+50\cdot3 =60+500+320+150 =1030

tall. Her er det nettopp den lille kjernen og de smale faktorene som gir komprimeringen.

Hurtigsjekk 57. For $\mathcal X\in\mathbb R^{20\times15\times10}$ brukes Tucker-størrelser $(4,3,2)$ . Oppgi dimensjonene til $\mathcal G,A,B,C$ , og sammenlign antall lagrede tall i full tensor og Tucker-formen.

Løsning

Steg 1: Dimensjonene er

\mathcal G:4\times3\times2,\quad A:20\times4,\quad B:15\times3,\quad C:10\times2.

Steg 2: Full tensor krever

20\cdot15\cdot10=3000

tall.

Steg 3: Tucker-formen krever

4\cdot3\cdot2+20\cdot4+15\cdot3+10\cdot2 =24+80+45+20=169

tall, før eventuell administrativ informasjon.

Tucker-formler for matrisering

For

\mathcal Y=\mathcal G\times_1A\times_2B\times_3C

gjelder

Y_{(1)}=AG_{(1)}(C\otimes B)^\top,

Y_{(2)}=BG_{(2)}(C\otimes A)^\top,

Y_{(3)}=CG_{(3)}(B\otimes A)^\top.

Tucker bruker Kronecker-produktet fordi kjernen kan koble alle kombinasjoner av faktorretninger. CP bruker Khatri–Rao fordi bare samsvarende kolonner kobles.

I den første formelen bygger $A$ ut modus $1$ , $G_{(1)}$ inneholder blandingen fra kjernen, og $C\otimes B$ lister alle kombinasjoner fra modus $3$ og $2$ . De to andre formlene er den samme ideen sett fra en annen modus.

SVD-analogien virker også baklengs:

M=U\Sigma V^\top \quad\Longrightarrow\quad \Sigma=U^\top MV =M\times_1U^\top\times_2V^\top.

Tilsvarende komprimeres Tucker-kjernen med

\mathcal G =\mathcal X\times_1A^\top\times_2B^\top\times_3C^\top

når faktorene har ortonormale kolonner.

Se dette i praksis

Se på modus- $1$ -formelen

Y_{(1)}=AG_{(1)}(C\otimes B)^\top.

Anta

A\in\mathbb R^{4\times2}, \qquad G_{(1)}\in\mathbb R^{2\times6}, \qquad C\otimes B\in\mathbb R^{15\times6}.

Da er

(C\otimes B)^\top\in\mathbb R^{6\times15},

og dimensjonskjeden blir

(4\times2)(2\times6)(6\times15) =4\times15.

Dermed er $Y_{(1)}\in\mathbb R^{4\times15}$ , som betyr at den rekonstruerte tensoren har modus- $1$ -størrelse $4$ og de to andre størrelsene ganger seg til $15$ .

Hurtigsjekk 58. La

A:5\times2,\qquad B:4\times3,\qquad C:6\times2,\qquad \mathcal G:2\times3\times2.

Finn dimensjonene til $G_{(1)}$ , $C\otimes B$ , $(C\otimes B)^\top$ og $Y_{(1)}$ .

Løsning

Steg 1: Modus- $1$ -matriseringen av kjernen har

G_{(1)}:2\times(3\cdot2)=2\times6.

Steg 2: Kronecker-produktet har

C\otimes B:(6\cdot4)\times(2\cdot3)=24\times6,

så transponeringen er $6\times24$ .

Steg 3: Dimensjonskjeden er

(5\times2)(2\times6)(6\times24)=5\times24.

Altså er $Y_{(1)}:5\times24$ , som passer en tensor av form $5\times4\times6$ .

Regn ut en liten Tucker-modell med tall

Vi rekonstruerer en $2\times2\times2$ -tensor med multirang høyst $(2,2,1)$ . Velg

G_{::1}=\begin{pmatrix}1&1\\0&2\end{pmatrix}, \quad A=\begin{pmatrix}1&1\\0&1\end{pmatrix}, \quad B=\begin{pmatrix}1&0\\1&1\end{pmatrix}, \quad C=\begin{pmatrix}1\\2\end{pmatrix}.

Fordi tredje kjernemodus har størrelse $1$ , lager vi først grunnmatrisen

H=AG_{::1}B^\top.

Regn fra midten og utover:

AG_{::1} =\begin{pmatrix}1&1\\0&1\end{pmatrix} \begin{pmatrix}1&1\\0&2\end{pmatrix} =\begin{pmatrix}1&3\\0&2\end{pmatrix},

H =\begin{pmatrix}1&3\\0&2\end{pmatrix} \begin{pmatrix}1&1\\0&1\end{pmatrix} =\begin{pmatrix}1&4\\0&2\end{pmatrix}.

Tallene i $C$ skalerer denne matrisen i de to lagene:

Y_{::1}=H=\begin{pmatrix}1&4\\0&2\end{pmatrix}, \qquad Y_{::2}=2H=\begin{pmatrix}2&8\\0&4\end{pmatrix}.

De ikke-null kjerneoppføringene gir også

\mathcal Y =a_1\circledcirc b_1\circledcirc c_1 +a_1\circledcirc b_2\circledcirc c_1 +2a_2\circledcirc b_2\circledcirc c_1.

Midterleddet er en Tucker-krysskobling mellom $a_1$ og $b_2$ .

Higher-Order Singular Value Decomposition

Navnet HOSVD er mye verre enn selve oppskriften: matrisér i hver retning, kjør den SVD-en du allerede kjenner, og behold de viktigste kolonnene.

HOSVD finner en Tucker-type modell ved å bruke SVD på hver matrisering. Med ønskede størrelser $(r_1,r_2,r_3)$ er dette en trunkert HOSVD:

La $A$ være de $r_1$ ledende venstre singulærvektorene til $X_{(1)}$ .
La $B$ være de $r_2$ ledende venstre singulærvektorene til $X_{(2)}$ .
La $C$ være de $r_3$ ledende venstre singulærvektorene til $X_{(3)}$ .
Beregn kjernen

\mathcal G =\mathcal X\times_1A^\top\times_2B^\top\times_3C^\top.

Returner $\mathcal G,A,B,C$ og eventuelt

\widehat{\mathcal X} =\mathcal G\times_1A\times_2B\times_3C.

Visste du at?

Eksamenssnarvei: HOSVD uten dimensjonskaos.

Se etter: Målstørrelsene $(r_1,r_2,r_3)$ forteller hvor mange retninger du skal beholde i hver modus.
Raskeste vei: Skriv først $X_{(1)}:m\times(np)$ , $X_{(2)}:n\times(mp)$ og $X_{(3)}:p\times(mn)$ . Ta så henholdsvis $r_1,r_2,r_3$ venstre singulærvektorer.
Vanlig felle: Ikke velg høyre singulærvektorer, og ikke kall $(r_1,r_2,r_3)$ én CP-rang. Trunkert HOSVD har heller ikke den samme eksakte Eckart–Young-optimaliteten som matrise-SVD.
Kontroll: $A:m\times r_1$ , $B:n\times r_2$ , $C:p\times r_3$ , og kjernen må bli $r_1\times r_2\times r_3$ . Faktorene fra SVD har ortonormale kolonner.

Se dette i praksis

\mathcal X\in\mathbb R^{6\times5\times4}

og velg Tucker-størrelser

(r_1,r_2,r_3)=(2,2,1).

HOSVD utfører tre SVD-er:

Ta SVD av $X_{(1)}\in\mathbb R^{6\times20}$ og behold to venstre singulærvektorer.
Ta SVD av $X_{(2)}\in\mathbb R^{5\times24}$ og behold to.
Ta SVD av $X_{(3)}\in\mathbb R^{4\times30}$ og behold én.

Dermed får vi

A\in\mathbb R^{6\times2},\qquad B\in\mathbb R^{5\times2},\qquad C\in\mathbb R^{4\times1},

\mathcal G =\mathcal X\times_1A^\top\times_2B^\top\times_3C^\top \in\mathbb R^{2\times2\times1}.

HOSVD har valgt de viktigste retningene separat i hver modus.

Hurtigsjekk 59. La $\mathcal Y\in\mathbb R^{8\times6\times5}$ og velg størrelser $(3,2,2)$ . Oppgi dimensjonene til de tre matriseringene, hvilke singulærvektorer som beholdes, og dimensjonene til $A,B,C,\mathcal G$ .

Løsning

Steg 1: Matriseringene er

Y_{(1)}:8\times30,\qquad Y_{(2)}:6\times40,\qquad Y_{(3)}:5\times48.

Steg 2: Behold henholdsvis $3$ , $2$ og $2$ ledende venstre singulærvektorer.

Steg 3: Derfor er

A:8\times3,\qquad B:6\times2,\qquad C:5\times2, \qquad \mathcal G:3\times2\times2.

Følg HOSVD med tall, linje for linje

La $\mathcal X\in\mathbb R^{2\times2\times2}$ ha

X_{::1}=\begin{pmatrix}3&0\\0&0\end{pmatrix}, \qquad X_{::2}=\begin{pmatrix}0&0\\0&1\end{pmatrix},

og velg $(r_1,r_2,r_3)=(1,1,1)$ . De eneste ikke-null oppføringene er $x_{111}=3$ og $x_{222}=1$ .

Med kursets kolonnerekkefølge er de tre matriseringene i dette symmetriske eksemplet identiske:

X_{(1)}=X_{(2)}=X_{(3)} =\begin{pmatrix} 3&0&0&0\\ 0&0&0&1 \end{pmatrix}.

Singulærverdiene er $3$ og $1$ , og den ledende venstre singulærvektoren er

e_1=\begin{pmatrix}1\\0\end{pmatrix}.

Dermed

A=B=C=e_1.

Kjernen er ett tall:

\mathcal G =\mathcal X\times_1e_1^\top\times_2e_1^\top\times_3e_1^\top =[3].

Rekonstruksjonen

\widehat{\mathcal X} =3e_1\circledcirc e_1\circledcirc e_1

beholder $x_{111}=3$ og kaster $x_{222}=1$ . Derfor

\|\mathcal X-\widehat{\mathcal X}\|_F=1, \qquad \frac{\|\mathcal X-\widehat{\mathcal X}\|_F}{\|\mathcal X\|_F} =\frac1{\sqrt{10}}.

Higher-Order Orthogonal Iteration

HOOI bruker HOSVD som start og forbedrer én faktormatrise om gangen:

Initialiser $A,B,C$ med HOSVD.
Gjenta:

\mathcal Z_A =\mathcal X\times_2B^\top\times_3C^\top,

og la $\widetilde A$ være de $r_1$ ledende venstre singulærvektorene til $(Z_A)_{(1)}$ .

Deretter

\mathcal Z_B =\mathcal X\times_1\widetilde A^\top\times_3C^\top,

og la $\widetilde B$ være de $r_2$ ledende venstre singulærvektorene til $(Z_B)_{(2)}$ .

Til slutt

\mathcal Z_C =\mathcal X\times_1\widetilde A^\top\times_2\widetilde B^\top,

og la $\widetilde C$ være de $r_3$ ledende venstre singulærvektorene til $(Z_C)_{(3)}$ .

Sett $A=\widetilde A$ , $B=\widetilde B$ , $C=\widetilde C$ , og stopp når feilen eller faktorene nesten ikke endrer seg. Beregn så

\mathcal G =\mathcal X\times_1A^\top\times_2B^\top\times_3C^\top.

Se dette i praksis

Anta at HOSVD har gitt startmatrisene

A^{(0)},\qquad B^{(0)},\qquad C^{(0)}.

Én HOOI-sveip oppdaterer dem i denne rekkefølgen:

Komprimer $\mathcal X$ med $B^{(0)}$ og $C^{(0)}$ . SVD-en av modus- $1$ -matriseringen gir $A^{(1)}$ .
Komprimer med den nye $A^{(1)}$ og gamle $C^{(0)}$ . SVD-en i modus $2$ gir $B^{(1)}$ .
Komprimer med nye $A^{(1)}$ og $B^{(1)}$ . SVD-en i modus $3$ gir $C^{(1)}$ .

Neste sveip starter med $A^{(1)},B^{(1)},C^{(1)}$ . HOOI er altså HOSVD-idéen gjentatt, med ny informasjon fra de andre modiene hver gang.

Hurtigsjekk 60. La $\mathcal X\in\mathbb R^{6\times5\times4}$ og $(r_1,r_2,r_3)=(2,2,1)$ . Finn formene til $\mathcal Z_A$ , $\mathcal Z_B$ og $\mathcal Z_C$ i én HOOI-sveip, og oppgi hvilke faktorer som er nye eller gamle i hvert steg.

Løsning

Steg 1: Med $B^\top:2\times5$ og $C^\top:1\times4$ får vi

\mathcal Z_A =\mathcal X\times_2B^\top\times_3C^\top \in\mathbb R^{6\times2\times1}.

Her brukes gamle $B$ og $C$ , og resultatet gir nye $A$ .

Steg 2: Bruk nye $A^\top:2\times6$ og gamle $C^\top:1\times4$ :

\mathcal Z_B \in\mathbb R^{2\times5\times1}.

Dette gir nye $B$ .

Steg 3: Bruk både nye $A^\top$ og nye $B^\top$ :

\mathcal Z_C \in\mathbb R^{2\times2\times4}.

Modus- $3$ -matriseringen har form $4\times4$ , og dens ledende venstre singulærvektor gir nye $C$ .

Bonus/utsyn: én numerisk HOOI-sveip

Bruk HOSVD-eksemplet over med $(r_1,r_2,r_3)=(1,1,1)$ og start

A=B=C=e_1.

Første projeksjon er

\mathcal Z_A =\mathcal X\times_2e_1^\top\times_3e_1^\top =\begin{pmatrix}3\\0\end{pmatrix}.

Den ledende venstre singulærvektoren er fortsatt $e_1$ , så $\widetilde A=e_1$ . På samme måte får vi

\mathcal Z_B=\begin{pmatrix}3\\0\end{pmatrix} \Longrightarrow \widetilde B=e_1,

\mathcal Z_C=\begin{pmatrix}3\\0\end{pmatrix} \Longrightarrow \widetilde C=e_1.

Kjernen er fortsatt $[3]$ , og feilen er fortsatt $1$ . Eksemplet er med vilje stasjonært: HOSVD-starten var allerede et fast punkt. På generelle data endres retningene. Eksakte blokkoppdateringer skal ikke forverre tilpasningen, men HOOI garanterer ikke et globalt minimum.

Oppsummering

Tensorer generaliserer skalarer, vektorer og matriser til flere modi.
Fibre oppstår når alle unntatt én indeks festes; snitt oppstår når én indeks festes.
Ytre produkter lager rang- $1$ -tensorer, og tensor-rang er det minste antallet slike byggeklosser i en eksakt sum.
Vektorisering, Kronecker, Khatri–Rao og Hadamard er forskjellige operasjoner med forskjellige dimensjonskrav.
Matrisering flytter tall til en matrise, mens et $k$ -modusprodukt transformerer én retning og oppfyller $Y_{(k)}=QX_{(k)}$ .
CP bruker samsvarende faktortripler; ALS finner faktorene ved vekslende minste-kvadraters problemer.
Tucker bruker en liten kjerne og én faktormatrise per modus.
HOSVD gir en Tucker-start fra SVD-er av matriseringene; HOOI forbedrer faktorene iterativt.

Din vurderingHva vil du ta med videre?

Hvordan kjentes denne delen?

Hva vil du se på igjen?Lagres bare i denne nettleseren. Ikke skriv helseopplysninger, fødselsnummer, passord eller private opplysninger om andre.

Sjekker lokal lagring …

SVD, matriser og tensorer

Del 1 · Matrisefaktorisering og egenverdidekomponering

Hvorfor faktoriserer vi en matrise?

Motivasjon

Lavrang-idé for lagring

Egenverdidekomponering som utgangspunkt

Påminnelse: egenverdier og egenvektorer

Eksempel: diagonaliserbar matrise

Geometrisk betydning

Appendiks: egenverdiberegning og to snarveier i nullrommet

Hvorfor egenverdier ikke er nok

Begrensninger ved egenverdidekomponering

Eksempel: ikke-diagonaliserbar matrise

Del 2 · Singulærverdidekomponering

Ortogonale matriser

SVD-setningen

Formen til Σ\SigmaΣ

Bevisidé: hvorfor finnes SVD?

Full, redusert/økonomi og kompakt SVD

Transponering og symmetriske matriser

Transponeringsegenskapen

Sammenhengen med A⊤AA^\top AA⊤A og AA⊤AA^\topAA⊤

Symmetriske matriser

Oppskrift for håndregning

SVD finnes selv når diagonalisering feiler

Hovedeksempel: en komplett håndregnet redusert SVD

SVD er en maskin med tre steg

Del 3 · Geometri, matriseegenskaper og beste lavrang-approksimasjon

Geometrien: V⊤V^\topV⊤, så Σ\SigmaΣ, så UUU

Rang-1-summen og virkningen på en vektor

Rang og singulærverdier lik null

Hva SVD avslører uten at vi bygger opp AAA

Trunkert SVD

Eckart–Young-teoremet

Eksempel: beste rang-1-approksimasjon

Hvorfor teoremet er optimalt

Lagring av en trunkert SVD

Del 4 · Moore–Penrose-inversen

Fra invers til pseudoinvers

Fire tilfeller, fire utregninger

Høye matriser: minste kvadrater

Brede matriser: løsningen med minst norm

Generell rangmangel: best tilpasning først, minst norm deretter

Eksempel fra den håndregnede SVD-en

Del 5 · Trunkert SVD og L-kurvemetoden

Små singulærverdier og støy

Hvorfor er støy et problem?

Trunkering av små singulærverdier

Oppdeling av feilen

Regulariseringsfeil uttrykt med koeffisienter

Valg av kkk i stedet for ε\varepsilonε

L-kurvemetoden

Oppsummering

Del 6 · Tensorer

Hva er en tensor?

Motivasjon

Definisjon av en tensor

Eksempler på tensorordener

Notasjon

Del 7 · Indeksering av tensorer

Orden, fibre og snitt

Fibre: fest alle unntatt én indeks

Snitt: fest én indeks

Del 8 · Indre og ytre produkter

Ytre produkter og tensor-rang

Ett mønster, skalert gjennom snittene

Klassisk indreprodukt

Klassisk ytre produkt

Tensorens ytre produkt

Tensor-rang

Praktisk faktormatrisenotasjon

Del 9 · Matriseoperasjoner

Vektorisering og tre ulike produkter

Ikke kjenn igjen et produkt bare på symbolet

Vektorisering

Kronecker-produkt

Khatri–Rao-produkt

Hadamard-produkt

Del 10 · Tensoroperasjoner

Matrisering og kkk-modusproduktet

Formen til $\Sigma$

Sammenhengen med $A^\top A$ og $AA^\top$

Geometrien: $V^\top$ , så $\Sigma$ , så $U$

Hva SVD avslører uten at vi bygger opp $A$

Valg av $k$ i stedet for $\varepsilon$

Matrisering og $k$ -modusproduktet

$k$ -modusproduktet

Vektortilfellet av $k$ -modusproduktet