
\section{ Least Squares }\index{Least squares}

Consider the linear system $L(x)=v$, where $L:U\stackrel{\text{linear}}{\longrightarrow}W$, and $v\in W$ is given. As we have seen, this system may have no solutions, a unique solution, or a space of solutions.  
But if $v$ is not in the range of $L$ then there will {\it never} be any solutions for $L(x)=v$.

However, for many applications we do not need a exact solution of the system; instead, we try to find the best approximation possible.  To do this, we try to find $x$ that minimizes $||L(x)-v||$.

\begin{quote}
``My work always tried to unite the Truth with the Beautiful, but when I had to choose one or the other, I usually chose the Beautiful.'' 

\vspace{-2mm}
\hspace{7cm}-- Hermann Weyl.
\end{quote}

This method has many applications, such as when trying to fit a (perhaps linear) function to a ``noisy'' set of observations.  For example, suppose we measured the position of a bicycle on a racetrack once every five seconds.  Our observations won't be exact, but so long as the observations are right on average, we can figure out a best-possible linear function of position of the bicycle in terms of time.

Suppose $M$ is the matrix for $L$ in some bases for $U$ and $W$, and~$v$ and~$x$ are given by column vectors $V$ and $X$ in these bases.  Then we need to approximate
\[
MX-V\approx 0
\]

Note that if $\dim U=n$ and $\dim W=m$ then $M$ can be represented by an $m\times n$ matrix and $x$ and $v$ as vectors in $\Re^n$ and $\Re^m$, respectively. Thus, we can write $W=L(U)\oplus L(U)^\perp$.  Then we can uniquely write $v=v^\parallel + v^\perp$, with $v^\parallel \in L(U)$ and $v^\perp \in L(U)^\perp$.  



Then we should solve $L(u)=v^\parallel$.  In components, $v^\perp$ is just $V-MX$, and is the part we will eventually wish to minimize.  

In terms of $M$, recall that $L(V)$ is spanned by the columns of $M$.  (In the natural basis, the columns of $M$ are $Me_1$, 
$\ldots$, $Me_n$.)  Then $v^\perp$ must be perpendicular to the columns of $M$.  \textit{i.e.}, $M^T(V-MX)=0$, or
\[
M^TMX = M^TV.
\]

Solutions $X$ to $M^TMX = M^TV$ are called \emph{least squares}\index{Least squares!solutions} solutions to $MX=V$.  

Notice that any solution $X$ to $MX=V$ is a least squares solution.  However, the converse is often false.  In fact, the equation $MX=V$ may have no solutions at all, but still have least squares solutions to $M^TMX = M^TV$.

Observe that since $M$ is an $m\times n$ matrix, then $M^T$ is an $n\times m$ matrix.  Then $M^TM$ is an $n\times n$ matrix, and is symmetric, since $(M^TM)^T=M^TM$.  Then, for any vector $X$, we can evaluate $X^TM^TMX$ to obtain a number.  This is a very nice number, though!  It is just the length $|MX|^2 = (MX)^T(MX)=X^TM^TMX$.

Now suppose that $\ker L=\{0\}$, so that the only solution to $MX=0$ is $X=0$; in particular, $M$ is invertible.  But if $M$ is invertible, then so is $M^TM$, since $(M^TM)^{-1} = M^{-1}M^{-T}$.  Then the only solution to $M^TMX=0$ is $X=0$.

In this case, the least squares solution (the $X$ that solves $M^TMX=MV$) is unique, and is equal to 
\[
X = (M^TM)^{-1}M^TV.
\]

In a nutshell, this is the least squares method.

\begin{itemize}
\item Compute $M^TM$ and $M^TV$.
\item Solve $(M^TM)X=M^TV$ by Gaussian elimination.
\end{itemize}


\begin{example}
Captain Conundrum\index{Captain Conundrum} falls off of the leaning tower of Pisa and makes three (rather shaky) measurements of his velocity at three different times.

\begin{center}
\begin{tabular}{c|c}
$t$ s & $v $ m/s \\ \hline
$1$ & $11$ \\
$2$ & $19$ \\
$3$ & $31$
\end{tabular}
\end{center}

Having taken some calculus\footnote{In fact, he is a \emph{Calculus Superhero}\index{Calculus Superhero}.}, he believes that his data are best approximated by a straight line
\[
v = at+b.
\]
Then he should find $a$ and $b$ to best fit the data.
\begin{eqnarray*}
11 &=& a\cdot 1 + b \\
19 &=& a\cdot 2 + b \\
31 &=& a\cdot 3 + b.
\end{eqnarray*}
As a system of linear equations, this becomes:

\[
\begin{pmatrix}
1 & 1 \\
2 & 1 \\
3 & 1 \\
\end{pmatrix}
\colvec{a\\b} \stackrel{?}{=}
\colvec{11\\19\\31}.
\]
There is likely no actual straight line solution, so instead solve $M^TMX=M^TV$.

\[
\begin{pmatrix}
1 & 2 & 3 \\
1 & 1 & 1 \\
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
2 & 1 \\
3 & 1 \\
\end{pmatrix} \colvec{a\\b}
= 
\begin{pmatrix}
1 & 2 & 3 \\
1 & 1 & 1 \\
\end{pmatrix}
\colvec{11\\19\\31}.
\]
This simplifies to the system:

\[
\begin{amatrix}{2}
14 & 6 & 142 \\
6 & 3 & 61
\end{amatrix}
\sim
\begin{amatrix}{2}
1 & 0 & 10 \\
0 & 1 & \frac{1}{3}
\end{amatrix}.
\]
Then the least-squares fit is the line

\[
v = 10\ t + \frac{1}{3}.
\]
Notice that this equation implies that Captain Conundrum accelerates towards Italian soil at 10 m/s$^2$ (which is an excellent
approximation to reality) and that he started at a downward velocity of $\frac13$ m/s (perhaps somebody gave him a shove....)!

\end{example}


















\section*{References}
\begin{itemize}
\item Hefferon, Chapter Three, Section VI.2: Gram-Schmidt Orthogonalization
\end{itemize}

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Linear_least_squares}{Linear Least Squares}
\item \href{http://en.wikipedia.org/wiki/Least_squares}{Least Squares}
\end{itemize}


\section*{Review Questions}

\begin{enumerate}
\item Let $L:U\rightarrow V$ be a linear transformation.  Suppose $v\in L(U)$ and you have found a vector $u_{\rm ps}$ that obeys $L(u_{\rm ps})=v$.

Explain why you need to compute $\ker L$ to describe the solution space of the linear system $L(u)=v$.

\item Suppose that $M$ is an $m\times n$ matrix with trivial kernel.  Show that for any vectors $u$ and $v$ in $\Re^m$:
\begin{itemize}
\item $u^TM^TMv = v^TM^TMu$
\item $v^TM^TMv \geq 0$.
\item If $v^TM^TMv=0$, then $v=0$.
\end{itemize}
(Hint: Think about the dot product in $\Re^n$.)


\end{enumerate}


\newpage
