MATH 414 Lecture 4

« previous | Wednesday, January 22, 2014 | next »

Least Squares

Given time $t$, we can measure samples of a function $y(t)$ as points $y_k$ for $k=1,2,\dots$.

Suppose we want to find a linear regression $y=at+b$ for parameters $a$ and $b$ that minimizes the following sum of squares:

$\sum _{k=0}^{n-1}{(y_k-(ak+b))}^2$

Case

Let us define $\overrightarrow{y}=a\overrightarrow{t}+b\overrightarrow{1}$, where $\overrightarrow{t}=⟨0,1,2,\dots ,n-1⟩$ and $\overrightarrow{1}=⟨1,1,\dots ,1⟩$.

Then $\sum _{k=0}^{n-1}(y_n-(ak+b))={({\overrightarrow{y}}_D-\overrightarrow{y})}^T({\overrightarrow{y}}_D-\overrightarrow{y})={\Vert {\overrightarrow{y}}_D-\overrightarrow{y}\Vert }^2$, where ${\overrightarrow{y}}_D$ is our vector of samples.

Let $W:=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{\overrightarrow{1},\overrightarrow{t}\}$ be a vector space of all possible regressions for $y$. For some unit vector $\hat{w}\in W$, we can find a vector $t\hat{w}$ such that $t\hat{w}=\overrightarrow{y}-{\overrightarrow{y}}_0$.

Therefore we can find a minimum value for $t$ in ${\Vert {\overrightarrow{y}}_D-({\overrightarrow{y}}_0+t\hat{w})\Vert }^2$:

$\begin{array}{rl}\Vert {\overrightarrow{y}}_D-({\overrightarrow{y}}_0+t\hat{w})\Vert & =⟨{\overrightarrow{y}}_D-({\overrightarrow{y}}_0+t\hat{w}),{\overrightarrow{y}}_D-({\overrightarrow{y}}_0+t\hat{w})⟩\\ & =\dots \\ & =t^2-2t⟨y_D-y_0,\hat{w}⟩\end{array}$

We find the minimum of this function at $t=0$, so we find that $⟨{\overrightarrow{y}}_D-{\overrightarrow{y}}_0,\hat{w}⟩=0$ and furthermore $⟨{\overrightarrow{y}}_D-{\overrightarrow{y}}_0,\overrightarrow{y}⟩=0$ for all $\overrightarrow{y}\in W$.

Punchline

Theorem. Let $V$ be an inner product space and let $W\subset V$ be a subspace of $V$. Also, let $\overrightarrow{v}$ be any vector in $V$. Then, ${\overrightarrow{w}}_0$ minimizes $\Vert \overrightarrow{v}-\overrightarrow{w}\Vert$ over all $\overrightarrow{w}\in W$ if and only if $\overrightarrow{v}-{\overrightarrow{w}}_0\perp W$.

Proof. Follows mutatis mutandis from the special case illustrated above.

quod erat demonstrandum

Finding ${\overrightarrow{w}}_0$

How do we find ${\overrightarrow{w}}_0$ (or in the special case ${\overrightarrow{y}}_0$)?

${\overrightarrow{w}}_0$ is the orthogonal projection of $\overrightarrow{v}$ onto the vector space $W$.

Let $\{{\hat{e}}_1,{\hat{e}}_2,\dots ,{\hat{e}}_n\}$ be an orthonormal basis for $W$. Then

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_W\left(\overrightarrow{v}\right)=\sum _{k=1}^n⟨\overrightarrow{v},{\hat{e}}_k⟩{\hat{e}}_k$