\input{preamble}

\title{2 - 6 - HVA ER EN KATT? - LF}

%isolert

\begin{document}
\pagenumbering{gobble}

\maketitle

\begin{oppgave}{1}
    Jeg beregna faktisk den inverse i oppgave 2-9 i økt 2-4, 
    det er bare å transponere $A$ og så skalerer radene litt:
    \begin{align*}
        A^{-1}=
    \begin{pmatrix}
        \frac{1}{2} & 0 & 0  \\
        0 & \frac{1}{4} & 0 \\
        0 & 0 & \frac{1}{4} 
    \end{pmatrix}
    \begin{pmatrix}
        1 & 0 & -1  \\
        1 & -\sqrt{2} & 1 \\
        1 & \sqrt{2} & 1 
    \end{pmatrix}
    \end{align*}
\end{oppgave}

\begin{oppgave}{2}
    Her er det viktig å forstå at dersom $P$ er en 
    matrise med ortonormale kolonner,
    er 
    \[
      P^{-1} = P^T
    \]
    og dette gjelder ikke for 
    \[
      V=
      \left(\;\begin{matrix}
      1 & 0 & 4 \\
      2 & 1 & -1 \\
      2 & -1 & -1
      \end{matrix}\;\right),
    \]
    for 
    \[
      VV^T= 
      V^TV=
      \left(\;\begin{matrix}
      1 & 2 & 2 \\
      0 & 1 & -1 \\
      4 & -1 & -1
      \end{matrix}\;\right)
      \left(\;\begin{matrix}
      1 & 0 & 4 \\
      2 & 1 & -1 \\
      2 & -1 & -1
      \end{matrix}\;\right)
      =
      \left(\;\begin{matrix}
      9 & 0 & 0 \\
      0 & 2 & 0 \\
      0 & 0 & 18
      \end{matrix}\;\right),
    \]
    men om vi normaliserer kolonnene og definerer 
    \[
      P=
      \left(\;\begin{matrix}
      1/3 & 0 & 4/\sqrt{18} \\
      2/3 & 1/\sqrt{2} & -1/\sqrt{18} \\
      2/3 & -1/\sqrt{2} & -1/\sqrt{18}
      \end{matrix}\;\right),
    \]
    er
    \[
      PP^T= 
      P^TP=
      \left(\;\begin{matrix}
      1 & 0 & 0 \\
      0 & 1 & 0 \\
      0 & 0 & 1
      \end{matrix}\;\right).
    \]
    Du kan nå sjekke selv at 
    \[
      A=P\Lambda P^T.
    \]
  \end{oppgave}
  
  
  
  \begin{oppgave}{3}
    Vi beregner først det karakteristiske polynomet 
    \begin{align*}
      \det 
      \begin{pmatrix}
        2-\lambda & 1 & 1 \\
        1 & 2-\lambda & 1 \\
        1 & 1 & 2-\lambda 
      \end{pmatrix} 
      =&\;(2-\lambda)\left( (2-\lambda)^2 - 1 \right) - (2-\lambda - 1) + (1-(2-\lambda))\\ 
      =&\;(2- \lambda)\left( 3-4\lambda+\lambda^2\right) - (1-\lambda ) - (1 -\lambda)\\[2mm]
      =&\;(2- \lambda)(3- \lambda)(1 - \lambda) - (1-\lambda ) - (1 -\lambda)\\[2mm]
      =&\;(1 - \lambda)((2- \lambda)(3- \lambda) - 2)\\[2mm]
      =&\;(1 - \lambda)(4 - 5\lambda +\lambda^2)\\[2mm]
      =&\;(1 - \lambda)(1 - \lambda)(4 - \lambda)\\[2mm]
    \end{align*}
    og ser at vi har en enkel egenverdi $\lambda = 4$ og en dobbel egenverdi $\lambda = 1$. 
    La oss begynne med den enkle egenverdien. 
    Vi kunne gausset i vei, 
    men siden vi elsker tall og observerer at tverrsummen av alle radene er 4,
    må egenvektoren være
    \[
    \mathbf v_1
    =
    \begin{pmatrix}
    1 \\
    1 \\
    1 
    \end{pmatrix}.
    \]
    Så den doble. 
    Siden
    \[
    \begin{pmatrix}
    1 & 1 & 1 \\
    1 & 1 & 1 \\
    1 & 1 & 1 \\
    \end{pmatrix}
    \sim 
    \begin{pmatrix}
    1 & 1 & 1 \\
    0 & 0 & 0 \\
    0 & 0 & 0 \\
    \end{pmatrix}
    \]
    ser vi at alle egenvektorer ligger i planet til likningen
    \[
    x_1 + x_2 + x_3 = 0
    \]
    så for eksempel 
    \[
    \mathbf v_2
    =
    \begin{pmatrix}
    1 \\
    -1 \\
    0
    \end{pmatrix}
    \hspace{10mm}
    \text{og}
    \hspace{10mm}
    \mathbf v_3
    =
    \begin{pmatrix}
    1 \\
    0 \\
    -1 
    \end{pmatrix}
    \]
    duger. 
    Merk at begge er ortogonale på $\mathbf v_1$,
    men ikke på hverandre.
    Heldigvis er vi flinke i projeksjon, 
    og ser at hvis vi 
    bytter ut $\V v_3$ med 
    \[
      \V v_2 - \frac{\V v_2^T\V v_3}{\V v_3^T\V v_3} \V v_3=
      \begin{pmatrix}
        1 \\
        -1\\
        0 
      \end{pmatrix}
      -
      \frac{1}{2}
      \begin{pmatrix}
        1 \\
        0 \\
        -1 
      \end{pmatrix}
      =
      \frac{1}{2}
      \begin{pmatrix}
        1 \\
        -2 \\
        1 
      \end{pmatrix}
    \]
    så er denne fortsatt egenvektor, 
    men også
    ortogonal på både $\V v_1$ og $\V v_2$. 
    Dersom vi normaliserer alle egenvektorer og 
    setter dem opp som kolonner i en matrise 
    \[
    V
    =
    \begin{pmatrix}
    1/\sqrt{3}  & 1/\sqrt{2} & 1/\sqrt{6}\\
    1/\sqrt{3}  & 0 & -2/\sqrt{6}\\
    1/\sqrt{3}  & -1/\sqrt{2} & 1/\sqrt{6}\\
    \end{pmatrix}
    \]
    vil 
    $
    A=
    VDV^T
    $,
    der
    \[
    D=
    \begin{pmatrix}
    4 & 0 & 0 \\
    0 & 1 & 0 \\
    0 & 0 & 1 \\
    \end{pmatrix}.
    \]
    Merk at egenvektorene som korresponderte til forskjellige egenverdier 
    automatisk kom ut ortogonale. 
    Dette var ikke tilfeldig, 
    for 
    \[
      \lambda_1 \V v_1^T\V v_2 = 
      (\lambda_1 \V v_1)^T\V v_2 = 
      (A \V v_1)^T\V v_2 = 
      \V v_1^T A^T \V v_2 = 
      \V v_1^T (A \V v_2) = 
      \V v_1^T (\lambda_2 \V v_2) = 
      \lambda_2\V v_1^T  \V v_2 
    \]
    slik at 
    \[
      \lambda_1 \V v_1^T\V v_2 = 
      \lambda_2\V v_1^T  \V v_2 
    \]
    eller 
    \[
      (\lambda_1 \V 
      -\lambda_2) \V v_1^T  \V v_2 = 0.
    \]
    Dersom $A$ er symmetrisk og $\lambda_1\neq \lambda_2$ må altså $\V v_1^T  \V v_2 =0$. 
  \end{oppgave}
  
  

\begin{oppgave}{4}
    Dette er litt greit å vite, 
    for det blir lettere å lese statistikkbøker 
    om man er god i lineæralgebra. 
    \begin{align*}
    \V 1^T \V 1  &= n \\[2mm]
    \V 1 \V 1^T &= 
    \begin{pmatrix}
        1 & 1 & \cdots & 1 & 1\\
        1 & 1 & \cdots & 1 & 1\\
        \vdots &   & \ddots &  & \vdots\\
        1 & 1 & \cdots & 1 & 1\\
        1 & 1 & \cdots & 1 & 1\\
    \end{pmatrix}\\[2mm]
     \V 1^T \V x &= n \overline{\V x}
    \end{align*}
\end{oppgave}


\begin{oppgave}{5}
    En projeksjon er en lineæroperator som tilfredsstiller $P=P^2$. 
    Vi beregner 
    \begin{align*}
         C_n^2=&
         \left( I - \frac{1}{n}\V 1 \V 1^T \right) 
         \left( I - \frac{1}{n}\V 1 \V 1^T \right) \\[2mm]
         =&
         I - \frac{2}{n} \V 1 \V 1^T + \frac{1}{n} \V 1 \V 1^T \\[2mm]
         =&
         I - \frac{1}{n} \V 1 \V 1^T 
    \end{align*}
    Gjennnomsnittet til den sentrerte variabelen er selvfølgelig null. 
    Det er det som er poenget. 
\end{oppgave}



\begin{oppgave}{6}
    Med sentrerte variable der $\overline{\V x} = \overline {\V y} = 0$, 
    får vi 
    \[
        \beta_1 = \frac{ \mathbf{x}^T \mathbf{y}}{\V x^T \V x}
        \hspace{10mm}
        \text{og}
        \hspace*{10mm}
        \beta_0 = 0.
    \]
    Nå kjenner vi igjen $\beta_1$ som projeksjonen av $\V y$ på $\V x$. 
\end{oppgave}


\begin{oppgave}{7}
    Vi har 
\[
    \V y = \beta_{10} \V x_1 + \beta_{01} \V x_2 + \beta_0 \V 1
\]
altså
\[
    \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}.
\]  
    La nå
    \begin{align*}
    \begin{pmatrix}
        x_{11} & x_{12} & 1 \\
        x_{21} & x_{22} & 1\\
        \vdots & \vdots &\vdots  \\
        x_{n1} & x_{n2} & 1
    \end{pmatrix}.
    \end{align*}
    Vi ganger med $A^T$ fra venstre for å få normallikningene: 
    \begin{align*}
        A^T\V y = A^TA\beta 
    \end{align*}
    Skrevet ut på komponentform blir dette 
    \begin{align*}
        \begin{pmatrix}
            \V y^T \V x_1 \\[1mm]
            \V y^T \V x_2 \\[1mm]
            n\overline{\V y} 
        \end{pmatrix}
        =
        \begin{pmatrix}
            \|\V x_1\|^2 & \V x_1^T\V x_2 & n\overline{\V x_1} \\[1mm]
            \V x_1^T\V x_2 & \|\V x_2\|^2 &  n\overline{\V x_2}\\[1mm]
            n\overline{\V x_1} & n\overline{\V x_2} & n
        \end{pmatrix}
    \begin{pmatrix}
        \beta_{10} \\[1mm]
        \beta_{01} \\[1mm]
        \beta_{0} 
    \end{pmatrix}
    \end{align*}
    Dersom $\overline{\V x_1} =\overline{\V x_2} = \overline {\V y} = 0$, 
    blir dette mye enklere:
    \begin{align*}
        \begin{pmatrix}
            \V y^T \V x_1 \\[1mm]
            \V y^T \V x_2 \\[1mm]
            0 
        \end{pmatrix}
        =
        \begin{pmatrix}
            \|\V x_1\|^2 & \V x_1^T\V x_2 & 0 \\[1mm]
            \V x_1^T\V x_2 & \|\V x_2\|^2 &  0\\[1mm]
            0 & 0 & n
        \end{pmatrix}
    \begin{pmatrix}
        \beta_{10} \\[1mm]
        \beta_{01} \\[1mm]
        \beta_{0} 
    \end{pmatrix}
    \end{align*}
    og vi ser lett at $\beta_0 = 0$, 
    slik at likningssystemet blir 
    \begin{align*}
        \begin{pmatrix}
            \V y^T \V x_1 \\[1mm]
            \V y^T \V x_2 
        \end{pmatrix}
        =
        \begin{pmatrix}
            \|\V x_1\|^2 & \V x_1^T\V x_2 \\[1mm]
            \V x_1^T\V x_2 & \|\V x_2\|^2 
        \end{pmatrix}
    \begin{pmatrix}
        \beta_{10} \\[1mm]
        \beta_{01} 
    \end{pmatrix}
    \end{align*}
    Et klassisk triks for å kjapt løse $2\times 2$-matriser, 
    er å kjenne til formelen 
    \begin{equation*}
        \begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1}=
        \frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}.
    \end{equation*}        
    slik at 
    \begin{align*}
        \beta =&
        \left( A^TA \right)^{-1}A\V y \\[2mm]
        =&
        \frac{1}{\|\V x_1\|^2\|\V x_2\|^2-\left( \V x_1^T\V x_2 \right)^2}
        \begin{pmatrix}
            \|\V x_2\|^2 & -\V x_1^T\V x_2 \\[1mm]
            -\V x_1^T\V x_2 & \|\V x_1\|^2 
        \end{pmatrix}
        \begin{pmatrix}
            \V y^T \V x_1 \\[1mm]
            \V y^T \V x_2 
        \end{pmatrix}
    \end{align*}
    I dataanalyse er det også vanlig å dele ut standardavvikene. 
    Dette er det samme som å normalisere vektorer i lineæralgebra. 
    Gjør vi det, 
    blir det enda penere:
    \begin{align*}
        \beta =&
        \frac{1}{1-\left( \V x_1^T\V x_2 \right)^2}
        \begin{pmatrix}
            1 & -\V x_1^T\V x_2 \\[1mm]
            -\V x_1^T\V x_2 & 1
        \end{pmatrix}
        \begin{pmatrix}
            \V y^T \V x_1 \\[1mm]
            \V y^T \V x_2 
        \end{pmatrix}
    \end{align*}
\end{oppgave}




\begin{oppgave}{8}
    Empirisk kovarians mellom to datasett $\V x$ og $\V y$ ser slik ut
    \begin{align*}
        \frac{1}{n-1}\sum_k (x_k-\overline{\V x}) (y_k-\overline{\V y})
    \end{align*}
    og dersom vi sentrerer, 
    blir dette bare skalarproduktet mellom $\V x$ og $\V y$ delt på $n-1$. 
    Hvis du 
    ser nøye på $\frac{1}{n-1} X^T X$ 
    vil du se at hvert element er den empiriske kovariansen 
    mellom de forskjellige kolonnene i $X$ siden  
    $X^T X$ bare er skalarprodukter mellom kolonner i $X$.
\end{oppgave}


\begin{oppgave}{9}
    Alle matriser på formen $A^TA$ er positivt definitte om de har full rang, 
    og positivt semidefinitte om de ikke har det.\footnote{
        Full rang betyr maksimalt antall lineært uavhengige rader eller kolonner:\\
        \url{https://en.wikipedia.org/wiki/Rank_(linear_algebra)}
    }
    Dersom $A$ har full rang, 
    er 
    \begin{align*}
        0 < \|A\V x\|^2 = \V x^T A^T A \V x
    \end{align*}
    så lenge $\V x \neq \V 0$. 
    Dersom $A$ ikke har full rang, 
    er 
    \begin{align*}
        0 \leq \|A\V x\|^2 = \V x^T A^T A \V x
    \end{align*}
    siden det finnes $\V x \neq \V 0$ slik at $A\V x = \V 0$. 
\end{oppgave}



\begin{oppgave}{10}
    PCA er en teknikk for å projisere dataskyen inn på en retning i rommet slik at variansen 
    til det resulterende envariable datasettet blir maksimert:\\
    \url{https://en.wikipedia.org/wiki/Principal_component_analysis}\\
    Jeg har plaget dere med dette fordi det er sentralt i kunstig intelligens, 
    og skal du skjønne noe av dét er du nødt til å forstå lineæralgebra og statistikk. 
    La oss anta for enkelhets skyld at $X$ kun har to kolonner. 
    Vi ønsker å finne den retningen $\V p$ i koordinatsystemet der datamengden er 
    plotta slik at datamengden projisert på $\V p$ har så stor varians som mulig. 
    Produktet $X\V p$ er en lang kolonnevektor der element $k$ er 
    projeksjonen av datapunkt $k$ på $\V p$, 
    og dersom vi ønsker å maksimere summen av kvadratene av disse, 
    må vi maksimere 
    \begin{align*}
        \|X\V p\| = \V p^T X^T X \V p.
    \end{align*}
    Nå er det et standardresultat i numerisk analyse at om denne skal maksimeres, 
    må man velge $\V p$ som den egenvektoren til $X^TX$ med størst egenverdi. 
\end{oppgave}

\begin{oppgave}{11}
    Jeg er ikke ekspert på datatolkning, 
    men får egenverdier på 36 og 28, 
    så det betyr nok for alle praktiske formål ingen samvariasjon. 
    Hvis det hadde vært stor forskjell på dem ville det betydd at det var 
    mye variasjon når vi projiserte dataene på den ene egenvektoren og lite variasjon når vi projiserte på den andre. 
\end{oppgave}


\begin{oppgave}{13}
    De er ortogonalt diagonaliserbare siden de er reelle og symmetriske.
\end{oppgave}

\begin{oppgave}{14}
    Dersom $A$ har dimensjon $n\times p$, 
    har $A^TA$ og $V$ dimensjon $p \times p$
    mens $AA^T$ og $U$ er $n\times n$. 
\end{oppgave}

\begin{oppgave}{15}
    Dersom $\V v$ er en egenvektor til $A^TA$ med egenvektor $\lambda \neq 0$,
    kan vi gange likningen 
    \begin{align*}
        A^TA\V v = \lambda \V v
    \end{align*}
    med $A$ og få 
    \begin{align*}
        AA^TA\V v = \lambda A\V v
    \end{align*}
    som sier at $A\V v$ er en egenvektor til $AA^T$ med den samme egenverdien. 
    Dersom $\lambda = 0$ bryter dette sammen siden $A\V v = 0$ og nullvektoren 
    ikke klassifiserer som egenvektor. 
    Resonnementet den andre veien er likt, 
    og egenvektorene til $AA^T$ kaller vi $\V u$. 
    Egenverdiene må være større enn null,
    siden 
    \begin{align*}
        0 \leq \|A\V v\|^2 = \V v^T A^T A \V v = \lambda \V \|v\|^2.
    \end{align*}
\end{oppgave}


\begin{oppgave}{16}
    Beregningen i oppgaven over viser at dersom $\|\V v\| = 1$ er 
    \begin{align*}
        \|A\V v\| = \sqrt{\lambda}. 
    \end{align*} 
\end{oppgave}


\begin{oppgave}{17}
    I de foregående oppgavene har vi vist at 
    \[
        A\V v = \sqrt{\lambda} \V u    
    \]
    der $\V v$ er en egenvektor til $A^TA$ og 
    $\V u$ er en egenvektor til $AA^T$, 
    begge normaliserte og med egenverdi $\lambda \neq 0$.
    Setter vi opp alt dette i en matriselikning,
    får vi 
    \begin{align*}
        AV = U\Sigma
    \end{align*}
    der $\Sigma$ er en diagonal og kvadratisk matrise med singulærverdiene på diagonalen. 
    Dette kalles den \textbf{reduserte svd-faktoriseringen} til $A$. 
    Dersom $A^TA$ eller $AA^T$ har egenverdier som er null
    kan vi utvide faktoriseringen til å inkludere de korresponderende egenvektorene,
    men disse er sjelden nyttige i praktiske anvendelser.
    Svd-faktoriseringen til 
    \[
        A=
        \left(\;
        \begin{matrix}
        1 & 0\\  
        0 & 1\\  
        1 & 1 
        \end{matrix}
        \;\right)
    \] 
    finner vi ved å beregne egenverdier og egenvektorer til 
    \[
        A^TA=
        \left(\;
        \begin{matrix}
        2 & 1\\  
        1 & 2 
        \end{matrix}
        \;\right)
    \] 
    som er 
    \[
        \lambda_1 = 3 
        \hspace*{10mm} 
        \V v_1 =     
        \left(\;
        \begin{matrix}
        1/\sqrt{2}\\  
        1/\sqrt{2}
        \end{matrix}
        \;\right)
        \hspace*{10mm}
        \text{og}
        \hspace*{10mm}
        \lambda_2 = 1 
        \hspace*{10mm} 
        \V v_2 =     
        \left(\;
        \begin{matrix}
        1/\sqrt{2}\\  
        -1/\sqrt{2}
        \end{matrix}
        \;\right)
    \]
    og for
    \[
        AA^T=
        \left(\;
        \begin{matrix}
        1 & 0 & 1\\  
        0 & 1 & 1\\  
        1 & 1 & 2 
        \end{matrix}
        \;\right)
    \] 
    som er
    \[
        \lambda_1 = 3 
        \hspace*{4mm} 
        \V u_1 =     
        \left(\;
        \begin{matrix}
        1/\sqrt{6}\\  
        1/\sqrt{6}\\  
        2/\sqrt{6}
        \end{matrix}
        \;\right)
        \hspace*{4mm}
        \text{og}
        \hspace*{4mm}
        \lambda_2 = 1 
        \hspace*{5mm} 
        \V u_2 =     
        \left(\;
        \begin{matrix}
        1/\sqrt{2}\\  
        -1/\sqrt{2} \\
        0
        \end{matrix}
        \;\right)
        \hspace*{4mm}
        \text{og}
        \hspace*{4mm}
        \lambda_3 = 0 
        \hspace*{4mm} 
        \V u_3 =     
        \left(\;
        \begin{matrix}
        1/\sqrt{3}\\  
        1/\sqrt{3}\\  
        -1/\sqrt{3}
        \end{matrix}
        \;\right)
    \]
    Du kan nå selv sjekke at 
    \begin{align*}
        A= U\Sigma V^T 
        =
        \left(\;
        \begin{matrix}
        1/\sqrt{6} &  1/\sqrt{2} \\  
        1/\sqrt{6} &  -1/\sqrt{2} \\  
        2/\sqrt{6} &  0\\  
        \end{matrix}
        \;\right)
        \left(\;
        \begin{matrix}
        \sqrt{3} & 0 \\  
        0 & 1  
        \end{matrix}
        \;\right)
        \left(\;
        \begin{matrix}
        1/\sqrt{2} & 1/\sqrt{2}\\  
        1/\sqrt{2} & -1/\sqrt{2}
        \end{matrix}
        \;\right)
    \end{align*}
    Dette kalles egentlig \textbf{redusert svd}. 
    Vi kan inkludere den siste egenvektoren til $AA^T$, 
    og skrive
    \begin{align*}
        A
        =
        \left(\;
        \begin{matrix}
        1/\sqrt{6} &  1/\sqrt{2} & 1/\sqrt{3}\\  
        1/\sqrt{6} &  -1/\sqrt{2} & 1/\sqrt{3}\\  
        2/\sqrt{6} &  0 & -1/\sqrt{3}\\  
        \end{matrix}
        \;\right)
        \left(\;
        \begin{matrix}
        \sqrt{3} & 0 \\  
        0 & 1  \\
        0&0
        \end{matrix}
        \;\right)
        \left(\;
        \begin{matrix}
        1/\sqrt{2} & 1/\sqrt{2}\\  
        1/\sqrt{2} & -1/\sqrt{2}
        \end{matrix}
        \;\right)
    \end{align*}
    som kalles \textbf{full svd}.
\end{oppgave}


\begin{oppgave}{18}
    \url{https://folk.ntnu.no/mortano/python/katt/}
\end{oppgave}



\end{document}
