\input{preamble}

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

%isolert

\begin{document}
\pagenumbering{gobble}

\maketitle


\begin{oppgave}{1}
    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}{2}
    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}{3}
    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}


\[
    \V y = \beta_{10} \V x_1 + \beta_{01} \V x_2 + \beta_0 \V 1
\]
\[
    \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}
\]

\begin{oppgave}{4}
    og la
    \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}{5}
    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}{6}
    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 kan finnes $\V x \neq \V 0$ slik at $A\V x = \V 0$. 
\end{oppgave}



\begin{oppgave}{9}
    Dette var kanskje bittelitt i hardeste laget for TMA4106. 
    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. 
\end{oppgave}

\begin{oppgave}{11}
    Både
    $A^TA$ og $AA^T$ 
    er symmetriske, 
    og symmetriske matriser er som kjent ortogonalt diagonaliserbare.
\end{oppgave}

\begin{oppgave}{12}
    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}{13}
    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}{14}
    Beregningen i oppgaven over viser at dersom $\|\V v\| = 1$ er 
    \begin{align*}
        \|A\V v\| = \sqrt{\lambda}. 
    \end{align*} 
\end{oppgave}


\begin{oppgave}{15}
    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}{16}
    \url{https://folk.ntnu.no/mortano/python/katt/}
\end{oppgave}



\end{document}
