01_background.tex

\chapter{Background}
\label{chap:background}

\href{https://www.youtube.com/watch?v=TrZdG642M4g&index=1&list=PLpl-gQkQivXhdgUCdaUQcdb31CRe8Mm2y}{Watch this video before beginning.}

Before we begin we need a few matrix prerequisites. Let,
$f: \real^p \rightarrow \real$,
be a function from the $p$ dimensional real line to the real line.
Assume that $f$ is linear, i.e. $f(\bx) = \ba^t \bx$
Then $ \nabla f = \ba.$ That is, the function that
contains the elementwise derivatives of $f$ (the gradient)
is constant with respect to $x$. 

Consider now the symmetric matrix $\bA$
($p\times p$) and the quadratic form:
$$
f(\bx) =  \bx^t \bA \bx.
$$
Then  $ \nabla f = 2 \bA^t \bx.$ The second derivative matrix (Hessian)
(where the $i, j$ element is the derivative
with respect to the $i$ and $j$ elements of this vector)
is then $2 \bA $.

\section{Example}

Consider an example that we will become very familiar with, {\bf least squares}.
Let $\by$ be an array of dimension $n\times 1$ and 
$\bX$ be an $n\times p$ full rank matrix. Let $\bbeta$ be a
$p$ vector of unknowns. Consider trying to minimize the function:
$$
f(\bbeta) = ||\by -  \bX \bbeta||^2 = (\by - \bX \bbeta )^t (\by -  \bX \bbeta)
= \by^t \by - 2 \by^t \bX^t \bbeta + \bbeta^t \bX^t \bX \bbeta.
$$
The gradient of $f$ (with respect to $\bbeta$) is:
\begin{equation}
\label{eq:deriv}
\nabla f(\bbeta) = -2 \bX^t \by + 2 \bX^t\bX \bbeta.
\end{equation}
A useful result is that if $\bX$ is of full column rank then
$\bX^t \bX$ is square and full rank and hence invertible. Thus, we can
calculate the root of the gradient \eqref{eq:deriv} and obtain the solution:
$$
\bbeta = \xtxinv \bX^t \by. 
$$
We will talk about these solutions at length. Also, it remains
necessary to show that this is a minimum and not just an
inflection point. We can do this by checking a second derivative
condition. Taking the second derivative of \eqref{eq:deriv} we 
get
$$
2 \bX^t\bX,
$$
a positive definite matrix. Thus our solution is indeed a minimum.

\subsection{Coding example}

\href{https://www.youtube.com/watch?v=wW-4P7pl6E0&index=2&list=PLpl-gQkQivXhdgUCdaUQcdb31CRe8Mm2y}{Watch this video before beginning.}

Load the \texttt{mtcars} dataset in R with \texttt{data(mtcars)}.
Let's set our $\by$ vector as \texttt{y = mtcars\$mpg} and our
$\bX$ matrix as a vector of ones, horsepower and weight:
\texttt{x = cbind(1, mtcars\$hp, mtcars\$wt)}. Let's find the
value of $\bbeta$ that minimizes $|| \by - \bX \bbeta||^2$. 

\begin{verbatim}
> y = mtcars$mpg
> x = cbind(1, mtcars$hp, mtcars$wt)
> solve(t(x) %*% x) %*% t(x) %*% y
           [,1]
[1,] 37.22727012
[2,] -0.03177295
[3,] -3.87783074
> # Compare with the estimate obtained via lm
> coef(lm(mpg ~ hp + wt, data = mtcars))
(Intercept)          hp          wt 
37.22727012 -0.03177295 -3.87783074 
\end{verbatim}



\section{Averages}

\href{https://www.youtube.com/watch?v=GbcBLDS1VBw&index=3&list=PLpl-gQkQivXhdgUCdaUQcdb31CRe8Mm2y}{Watch this video before beginning.}

Consider some useful notational conventions we'll use. 
$\bone_n$ is an  $n$ vector containing only ones while
$\bone_{n\times p}$ is an $n\times p$ matrix containing ones.
$\bI$ is the identity matrix, which we will subscript if a
reminder of the dimension is necessary.

We denote by $\bar y$ the average of the $n$ vector $\by$.
Verify for yourself that $\bar y = \frac{1}{n} \by^t \bone_n = \frac{1}{n} \bone_n^t \by$.
Furthermore, note that $(\bone_n^t \bone_n)^{-1} = \frac{1}{n}$ so that
$$
\bar y = (\bone_n^t \bone_n)^{-1} \bone^t_n \by.
$$
Consider our previous least squares problem. If $\bX = \bone_n$ and $\bbeta$ 
is just the scalar $\beta$. The least squares function we'd like to minimize
is:
$$
(\by - \bone_n  \beta)^t (\by -  \bone_n \beta) = ||\by -  \bone_n\beta||^2.
$$
Or, what constant vector best approximates $\by$ it the terms of minimizing the
squared Euclidean distance? From above, we know that the solution is of the form 
$$
\bbeta = \xtxinv \bX^t \by
$$
which in this specific case works out to be:
$$
\bar y = (\bone_n^t \bone_n)^{-1} \bone^t_n \by.
$$
That is, the average is the best scalar estimate to minimize the 
Euclidean distance. 

\section{Centering}

Continuing to work with our vector of ones, note that 
$$
\by -  \bone_n \bar y
$$
is the centered version of $\by$ (in that it has the mean subtracted from each element of the $\by$ vector).
We can rewrite this as:
$$
\tilde \by = \by -  \bone_n \bar y= \by - (\bone_n^t \bone_n)^{-1} \bone^t \bone \by
= \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone^t \right\} \by.
$$
In other words, multiplication by the matrix $ \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone^t \right\}$
centers vectors. To check that $\tilde \by$ is centered, consider multiplying by $\bone_n$ (which sums its elements). 
$$
\bone_n^t \tilde \by = \bone_n^t \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\} \by
= \left\{ \bone_n^t - \bone_n^t \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\} =
\left\{ \bone_n^t - \bone_n^t \right\}\by = 0.
$$

This operation can be very handy for centering matrices. For example, if $\bX$ is an $n\times p$
matrix then the matrix $\tilde \bX  = \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone^t \right\} \bX$
is the matrix with every column centered. Conversely, right multiplication
by  $ \bI - \bone_p (\bone_p^t \bone_p)^{-1} \bone_p^t$ centers every row
of $\bX$.



\subsection{Coding example}

\href{https://www.youtube.com/watch?v=sixe0fUr5cg&list=PLpl-gQkQivXhdgUCdaUQcdb31CRe8Mm2y&index=4}{Watch this video before beginning.}

Let's take our $\bX$ matrix defined previously from the \texttt{mtcars} dataset and
mean center it. We'll contrast using matrix manipulations versus (preferable)
R functions. 

\begin{verbatim}
> n = nrow(x)
> I = diag(rep(1, n))
> H = matrix(1, n, n) / n
> xt = (I - H) %*% x 
> apply(xt, 2, mean)
[1] 0.000000e+00 0.000000e+00 2.168404e-16
> ## Doing it using sweep
> xt2 = sweep(x, 2, apply(x, 2, mean))
> apply(xt2, 2, mean)
[1] 0.000000e+00 0.000000e+00 3.469447e-17
\end{verbatim}


\section{Variance}

\href{https://www.youtube.com/watch?v=hTVkDOojbdw&index=5&list=PLpl-gQkQivXhdgUCdaUQcdb31CRe8Mm2y}{Watch this video before beginning.}


Consider the fact that the matrix $\left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\}$
is both symmetric and idempotent. The standard sample variance is the average squared deviation of the
observations from the sample mean (usually using $n-1$ rather than $n$). That is,
$$
S^2 = \frac{1}{n-1}|| \by -  \bone_n \bar y||^2 = \frac{1}{n-1} \tilde \by^t \tilde \by
$$
We can write out the norm component of this as: 
$$
\by^t \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\}
\left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\} \by
= \by^t \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\}\by.
$$
Thus, our sample variance is a fairly simple quadratic form. 
Notice the fact that the matrix $\left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\}$
is both symmetric and idempotent.

Similarly, if we have two vectors, $\by$ and $\bz$ then $\frac{1}{n-1}\by^t \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\} \bz$ is the
empirical correlation between them.
This is then useful for matrices. Consider that
$$
\frac{1}{n-1} \bX^t \left\{ \bI - \bone_n (\bone_n^t \bone_n)^{-1} \bone_n^t \right\} \bX
= \frac{1}{n-1} \tilde \bX^t \tilde \bX
$$
is a matrix where each element is the empirical covariance between columns of $\bX$.
This is called the variance/covariance matrix. 

\subsection{Coding example}

\href{https://www.youtube.com/watch?v=_AHZIy8PRmU&list=PLpl-gQkQivXhdgUCdaUQcdb31CRe8Mm2y&index=6}{Watch this video before beginning.}

Let's manually calculate the covariance of the \texttt{x} matrix from before.

\begin{verbatim}
> n = nrow(x)
> I = diag(rep(1, n))
> H = matrix(1, n, n) / n
> round(t(x) %*% (I - H) %*% x / (n - 1), 6)
     [,1]       [,2]      [,3]
[1,]    0    0.00000  0.000000
[2,]    0 4700.86694 44.192661
[3,]    0   44.19266  0.957379
> var(x)
     [,1]       [,2]      [,3]
[1,]    0    0.00000  0.000000
[2,]    0 4700.86694 44.192661
[3,]    0   44.19266  0.957379
\end{verbatim}
Recall, the first column was all ones; thus the row and column of zeros in the variance.