\input{preamble}

\title{7 - HVA ER EN KATT?}

%isolert

\begin{document}
\pagenumbering{gobble}

\maketitle


Nå skal vi se litt på hvordan lineæralgebra brukes i datahåndtering;
så og si alt vi har lært dette året kommer til nytte.
Vi skal ikke bry oss med \say{statistikk} som sådan, 
for i statistikk er man veldig opptatt av å skille mellom parametrene 
i sannsynlighetsmodellen som ligger til grunn
og estimatorene man stapper dataene inn i (for eksempel gjennomsnitt eller empirisk standardavvik).
Vi skal bry oss mest med lineæralgebraknepene.

\begin{oppgave}{1}
Da må vi først observerere noe gunstig om matriser med ortogonale kolonner. 
Finn den inverse til matrisen
\[
\begin{pmatrix}
1 & 1 & 1  \\
0 & -\sqrt{2} & \sqrt{2}  \\
-1 & 1 & 1 
\end{pmatrix}
\]
uten å gausseliminere - 
se heller på oppgave 9 i økt 2-4. 
\end{oppgave}

Vi sier at en reell matrise $P$ \textbf{ortogonal} dersom den har ortonormale kolonner,
og da er enkelt og greit
\[
P^{-1}=P^T.
\]
Dersom en matrise $n \times n$-matrise $A$ har 
$n$ ortogonale egenvektorer sier vi derfor at $A$ er
\textbf{ortogonalt diagonaliserbar},
og skriver
\[
A=P\Lambda P^T.
\]


\begin{oppgave}{2}
    Finn den ortogonale diagonaliseringen til 
    $
        \left(\;\begin{matrix}
            1 & 2 & 2 \\
            2 & 6 & 2 \\
            2 & 2 & 6
        \end{matrix}\;\right).
    $
\end{oppgave}


Vi sier at en reell matrise $A$ er \textbf{symmetrisk} dersom $A=A^T$. 
I anvendelser er det veldig vanlig at det dukker opp symmetriske matriser.
En reell matrise er ortogonalt diagonaliserbar 
hvis og bare hvis den er symmetrisk. 
Dette kalles \textbf{spektralteoremet},
og er ikke trivielt å vise, 
men det er heldigvis trivielt å huske.

\begin{oppgave}{3}
    Klarer du å ortogonalt diagonalisere
    $
        \left(\;\begin{matrix}
            2 & 1 & 1 \\
            1 & 2 & 1 \\
            1 & 1 & 2
        \end{matrix}\;\right)?
    $
\end{oppgave}

\begin{center}\includegraphics[scale=.27]{../figurer/L1019726}\end{center}

\clearpage

Som du kanskje ser av oppgaven over, 
kan en symmetrisk matrise fint ha en ikke-ortogonal egenvektorbasis,
men poenget er at du alltid kan finne en som er ortogonal. 
Hvordan vi finner en ortogonal diagonalisering for matrisen i oppgave 3 kommer vi tilbake. 
Nå tar vi litt om datahåndtering. 
Det er en matrise som er veldig praktisk,
nemlig kolonnevektoren
\[
    \V 1 = 
        \left(\;\begin{matrix}
            1 \\
            1 \\
            \vdots \\
            1 
        \end{matrix}\;\right)
\]
Det er ikke helt uvanlig å skrive $\V 1_n$ for å indikere dimensjon, 
men vanligvis er dette overflødig.

\begin{oppgave}{4}
    Regn ut $\V 1^T \V 1$,  $\V 1 \V 1^T$ og $\V 1^T \V x$.
\end{oppgave}

I faktiske anvendelser er det vanlig å \textbf{sentrere} datavektoren $\V x$
ved å lage en ny datavektor der man har 
trukket $\overline{\V x}$ fra alle komponentene i $\V x$,
og så jobbe med denne istedet. 
Med den nye vektoren $\V 1$ kan vi skrive den sentrerte variabelen som 
\[
    \V x - \overline{\V x} \cdot \V 1 
    =
    \begin{pmatrix}
        x_1\\
        x_2\\
        \vdots\\
        x_n
    \end{pmatrix}
    -\overline{\V x}\cdot
    \begin{pmatrix}
        1\\
        1\\
        \vdots\\
        1
    \end{pmatrix}
    =
    \begin{pmatrix}
        x_1\\
        x_2\\
        \vdots\\
        x_n
    \end{pmatrix}
    -
    \begin{pmatrix}
        \overline{\V x}\\
        \overline{\V x}\\
        \vdots\\
        \overline{\V x}
    \end{pmatrix}
    =
    \begin{pmatrix}
        x_1-\overline{\V x}\\
        x_2-\overline{\V x}\\
        \vdots\\
        x_n-\overline{\V x}
    \end{pmatrix}
    = 
    \left( I - \frac{1}{n}\V 1 \V 1^T \right)\V x
\]
Matrisen
\begin{align*}
     C_n=\left( I - \frac{1}{n}\V 1 \V 1^T \right) 
\end{align*}
kalles \textbf{sentreringsmatrisen} fordi den sentrerer $\V x$.  
Vi sier at en lineæroperator $P$ er en \textbf{projeksjon} dersom $P^2=P$. 
Dette betyr kort og godt at om du bruker lineæroperatoren to ganger etter hverandre,
skjer det ingenting når du bruker den for andre gang. 

\begin{oppgave}{5}
    Vis at $C_n$ er en projeksjon
    og finn gjennomsnittet til den nye sentrerte variabelen. 
\end{oppgave}

\begin{center}\includegraphics[scale=.27]{../figurer/L1002207}\end{center}

\clearpage

Med sentrerte variable blir livet greit.
I økt 2-6 utledet du uttrykket
\[
    \beta_1 = \frac{ \mathbf{x}^T \mathbf{y} - n \bar{\mathbf x} \bar{\mathbf y}}{\V x^T \V x - n\left( \bar{\mathbf x} \right)^2}
    \hspace{10mm}
    \text{og}
    \hspace*{10mm}
    \beta_0 = \overline{\mathbf y}-\beta_1\overline{\mathbf x}
\]
for koeffisientene til det rettlinjede regresjonspolynomet. 


\begin{oppgave}{6}
    Dette ser mye penere ut om $\V x$ og $\V y$ er sentrerte,
    og forklarer hvorfor noen sier at man \say{projiserer $\V y$ på $\V x$}
    når man kjører regresjon.
\end{oppgave}


Skjønte du forrige side, 
kan du gå med på at 
sentrerte variable er lurt. 
La oss spinne videre litt. 
\textbf{Multippel regresjon} handler om at 
forklaringsvariabelen har flere dimensjoner. 
Du kan for eksempel tenke at du har målt sylindervolum $\V x_1$ og vekt $\V x_2$ på $n$ biler, 
og så er responsvariabelen $\V y$ drivstofforbruk per kilometer. 
Hvis du ønsker å tilpasse et første ordens regresjonspolynom i to variable,
får du det overbestemte likningssettet
\[
    \V y = \beta_{10} \V x_1 + \beta_{01} \V x_2 + \beta_0 \V 1
\]
eller
\[
    \begin{pmatrix}
        y_1 \\
        y_2 \\
        \vdots \\
        y_n 
    \end{pmatrix}
    =
    \beta_{10}
    \begin{pmatrix}
        x_{11} \\
        x_{21} \\
        \vdots \\
        x_{n1}
    \end{pmatrix}
    +
    \beta_{01}
    \begin{pmatrix}
        x_{12} \\
        x_{22} \\
        \vdots \\
        x_{n2}
    \end{pmatrix}
    +
    \beta_0
    \begin{pmatrix}
        1 \\
        1 \\
        \vdots \\
        1
    \end{pmatrix}
\]
og dette kan angripes med minste kvadraters metode slik som i forrige uke. 

\begin{oppgave}{7}
    Regn ut formlene for regresjonskoeffisientene dersom $\V x_1$, $\V x_2$ og $\V y$ er sentrerte.
\end{oppgave}

La oss anta du har $n$ realiseringer av en $p$-dimensjonal 
tilfeldig variabel.
Det vanlig å sette disse opp i 
en $n \times p$-matrise:
\[
    X=
    \left(
        \begin{array}{c | c | c | c}
         &  & & \\
        \V x_1 &\V  x_2 & \cdots &\V  x_p \\
          &  & & 
        \end{array}
    \right)          
\]
Tenk at du måler lengde, 
bredde og høyde på alle plankene i en plankestabel,
og så sentrerer du hver av disse.
Til slutt setter du alt opp i matrisen $X$ på en slik måte 
at rad $k$ er de sentrerte målene til planke $k$.
Vi kaller $\frac{1}{n-1} X^T X$ den \textbf{empiriske kovariansmatrisen},
og den er en estimator for den antatte bakenforliggende kovariansmatrisen.\footnote{
    \url{https://en.wikipedia.org/wiki/Estimation_of_covariance_matrices}
}

\begin{oppgave}{8}
    Vis at elementene i  $\frac{1}{n-1} X^T X$ er den empiriske kovariansen mellom kolonnene i $X$.  
\end{oppgave}


\begin{center}\includegraphics[scale=.27]{../figurer/L1019717}\end{center}

\clearpage

Vi sier at en matrise $A$ er \textbf{positivt definitt} dersom 
\[
    \V x^T A \V x > 0 
\]
for alle $\V x$,
og \textbf{positivt semidefinitt} dersom 
\[
    \V x^T A \V x \geq 0 
\]
for alle $\V x$. 

\begin{oppgave}{9}
    Vis at den empiriske kovariansmatrisen er positivt semidefinitt. 
\end{oppgave}


I flervariabel statistikk finnes det noe som kalles 
\textbf{prinsipalkomponentanalyse}.\footnote{\url{https://en.wikipedia.org/wiki/Principal_component_analysis}}
Dette er en teknikk for å lete opp akser i datamengden 
der samvariasjonen er sterk. 
Teknikken baserer seg på å projisere $X$ inn på en retning $\V v$
slik at den empiriske variansen til de resulterende punktene blir maksimert.
Dette får man til ved å lete opp egenvektorene 
til de største egenverdiene til kovariansmatrisen. 

\begin{oppgave}{10}
    Forklar hvorfor egenvektorene til $X^TX$ forteller om samvariasjonen 
    mellom kolonnene i $X$.\\
    (Hint: Finn ut hva en \say{Rayleigh quotient} er.\footnote{\url{https://en.wikipedia.org/wiki/Rayleigh_quotient}})
\end{oppgave}

I TMA4245 skal du også drive med liknende ting mot slutten av semesteret, 
se her:\\
\url{https://tma4245.math.ntnu.no/forventing-og-varians/korrelasjon/}\\
og her:\\
\url{https://tma4245.math.ntnu.no/forventing-og-varians/kovarians/}

\begin{oppgave}{11}
    Er det samvariasjon mellom høyde og bredde i kaibordene fra sommeren 2023?\\
    \url{https://folk.ntnu.no/mortano/python/kai/kai.csv}
\end{oppgave}


Noen ganger er det regnet som ugunstig dersom kolonnene 
i datamatrisen har veldig forskjellig lengde. 
Dette fikser vi ved å dele ut standardavviket i hver kolonne, 
akkurat som når man normaliserer vektorer ellers i lineæralgebra. 

\begin{center}\includegraphics[scale=.27]{../figurer/L1003395}\end{center}


\clearpage

Nå skal vi se at det er faktisk ikke nødvendig å gange datamatrisen med 
seg selv for å finne kovariansmatrisen. 
Det finnes noe enda mer sofistiskert som heter SVD. 
La oss begynne med litt geometrisk fikling.

\begin{oppgave}{12}
    Skriv en rutine som tar inn 
    $A \in \mathbb{R}^{2\times 2}$ 
    og plotter $A\V x$ for alle $\V x$ på enhetssirkelen.
\end{oppgave}

Fikk du til dette, 
vil du oppdage at koden din alltid produserer 
ellipser, 
ihvertfall så lenge $A$ har linært uavhengige kolonner. 
La oss finne ut mer om disse ellipsoidene. 
Trikset er å studere 
$A^TA$ og $AA^T$. 
Vi lar $n > p$,
slik at $A$ er høyt og tynn og $A^T$ er lang og flat. 
Dette er ikke noen essensiell restriksjon, 
men vi gjør den fordi det hjelper litt på visualiseringen.

\begin{oppgave}{13}
    Både
    $A^TA$ og $AA^T$ 
    er ortogonalt diagonaliserbare. 
    Hvorfor?
\end{oppgave}

Siden 
$A^TA$ er ortogonalt diagonaliserbar,
finnes det et ortonormalt sett med egenvektorer. 
La oss sette disse opp i en ortogonal matrise $V$.
Det samme gjelder for $AA^T$; 
la oss sette disse egenvektoren opp i en ortonormal matrise $U$.

\begin{oppgave}{14}
    Hva er dimensjonene til 
    $A^TA$, $AA^T$, $V$ og $U$?\\
    Hvor mange av egenverdiene 
    til $AA^T$ kan være forskjellige fra null?
\end{oppgave}

Her er enda en observasjon.

\begin{oppgave}{15}
    Vis at dersom $\V v$ er 
    en egenvektor til $A^TA$ med egenverdi $\lambda$,
    er $A\V v$ en egenvektor til $AA^T$. 
    Hva er egenverdien? 
    Kan du si noe om fortegnet? 
\end{oppgave}


Hvis du skjønte forrige oppgave, 
skjønner du forhåpentligvis at $A^TA$ og $AA^T$ 
har de samme egenverdiene så
lenge du ser bort fra multiplisiteten til de egenverdiene som er null.
La oss nå anta at $\V v$ er en egenvektor til $A$ med lengde 1.

\begin{oppgave}{16}
    Hva er lengden til $A\V v$?
\end{oppgave}

Lengden til $A\V v$ kalles \textbf{singulærverdi},
og vi bruker bokstaven $\sigma_k$. 
Kolonnene i $U$ og $V$ kalles henholdsvis de \textbf{venstre og høyre singulærvektorene}.
Hvis du tenker nøye på alt du har gjort til nå, 
vil du se at det går an å skrive 
\[
    A = U\Sigma V^T
\]
der $\sigma$-ene sitter i den rektangulære diagonalmatrisen $\Sigma$.
Dette kalles \textbf{SVD-faktoriseringen}\footnote{\url{https://en.wikipedia.org/wiki/Singular_value_decomposition}} 
til $A$. 
Denne finnes alltid, 
og dersom du sorterer singulærverdiene i synkende rekkefølge 
($\sigma_1$ er størst) og velger alle positive,
er $\Sigma$ entydig. 
De unitære matrisene $U$ og $V$ vil ikke nødvendigvis være entydige, 
men de er det i noen tilfeller.

\begin{oppgave}{17}
    Hvordan ser $\Sigma$ ut?
    Finn svd-faktoriseringen til 
    \[
        A=
        \left(\;
        \begin{matrix}
        1 & 0\\  
        0 & 1\\  
        1 & 1 
        \end{matrix}
        \;\right)
    \] 
\end{oppgave}

Singulærverdidekomposisjonen er en av de viktigste matrisefaktoriseringene. 
Har du den har du mye,
og pythonkommandoen heter numpy.linalg.svd.
Nå skal vi se litt på hva svd kan brukes til. 
Det første er kompresjon. 
Vi kan skrive $A$ slik:
\begin{align*}
    A = \sigma_1\V u_1  \V v_1^* + 
    \sigma_2\V u_2  \V v_2^* + 
    \sigma_3\V u_3 \V v_3^* + \cdots +
    \sigma_r\V u_r  \V v_r^* 
\end{align*}
der $r$ er antallet singulærverdier som ikke er null. 
Vi ser nå at dersom det er bare er to av singulærverdiene som er over for eksempel maskinpresisjon, 
er all informasjon i matrisen inneholdt i uttrykket 
\begin{align*}
    A = \V u_1 \sigma_1 \V v_1^* + 
    \V u_2 \sigma_2 \V v_2^*.
\end{align*}

\begin{oppgave}{18}
    La oss lage et bilde av en katt. 
    Lag deg en matrise $A$ i python med tilfeldige tall mellom -1 og 1. 
    Dette er bakgrunnen. 
    Sett så ett element til 10 eller 100 eller noe sånt. 
    Dette er katten.
    Kjør svd på $A$ og skriv ut 
    \begin{align*}
        A - \V u_1 \sigma_1 \V v_1^*  
        \hspace*{10mm}
        \text{og}
        \hspace*{10mm}
        A - \left(\V u_1 \sigma_1 \V v_1^* + 
        \V u_2 \sigma_2 \V v_2^*\right).
    \end{align*}
            
\end{oppgave}


\section*{UKENS NØTTER}

Vi sier at lengden 
\[
\| \mathbf x \|=\sqrt{(\mathbf x, \mathbf x)}
\]
er \textbf{indusert} av indreproduktet $(\cdot, \cdot)$.
Men det finnes også lengder som ikke er indusert av et indreprodukt. 
Derfor har vi egne aksiomer for lengde: 
\begin{itemize}
\item $\| \mathbf x \| > 0$ dersom $\mathbf x \neq \mathbf 0$
\item $\| a\mathbf x \| =|a|\| \mathbf x \| $
\item $\| \mathbf x +\mathbf y \|\leq \| \mathbf x \| + \| \mathbf y \|$
\end{itemize}
På fagspråket sier man \textbf{norm} istedet for lengde.
Det finnes mange normer som ikke er indusert av indreprodukt


\begin{oppgave}{1}
Vis at 
$
\| \mathbf x \|_2=\sqrt{(\mathbf x, \mathbf x)}
$
er en lengde. 
\end{oppgave}

\begin{oppgave}{2}
Vis at 
$
\| \mathbf x \|_\infty = \max_{k} |x_k|
$
og 
$
\| \mathbf x \|_1 = \sum_{k} |x_k|
$
er lengder når $\mathbf x \in \mathbb C^n$. Forklar subskriptene. 
\end{oppgave}

Så har vi \textbf{matrisenormen}
$
\|A\|=\max_{\|\mathbf x\|=1} \|A\mathbf x \|.
$

\begin{oppgave}{3}
Vis at dette er en lengde. 
\end{oppgave}

\begin{oppgave}{4}
  Vis at $e^{A}$ er absolutt konvergent for alle $A$. 
\end{oppgave}

\begin{center}\includegraphics[scale=.27]{../figurer/L1019719}\end{center}

\end{document}
