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,\ldots$.

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

$\sum _{k=0}^{n-1}\left(y_{k}-(a\,k+b)\right)^{2}$

Case

Let us define ${\vec {y}}=a\,{\vec {t}}+b\,{\vec {1}}$, where ${\vec {t}}=\left\langle 0,1,2,\ldots ,n-1\right\rangle$ and ${\vec {1}}=\left\langle 1,1,\ldots ,1\right\rangle$.

Then $\sum _{k=0}^{n-1}\left(y_{n}-\left(a\,k+b\right)\right)=\left({\vec {y}}_{D}-{\vec {y}}\right)^{T}\,\left({\vec {y}}_{D}-{\vec {y}}\right)=\left\|{\vec {y}}_{D}-{\vec {y}}\right\|^{2}$, where ${\vec {y}}_{D}$ is our vector of samples.

Let $W:=\mathrm {Span} \left\{{\vec {1}},{\vec {t}}\right\}$ 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}}={\vec {y}}-{\vec {y}}_{0}$.

Therefore we can find a minimum value for $t$ in $\left\|{\vec {y}}_{D}-\left({\vec {y}}_{0}+t\,{\hat {w}}\right)\right\|^{2}$:

${\begin{aligned}\left\|{\vec {y}}_{D}-\left({\vec {y}}_{0}+t\,{\hat {w}}\right)\right\|&=\left\langle {\vec {y}}_{D}-\left({\vec {y}}_{0}+t\,{\hat {w}}\right),{\vec {y}}_{D}-\left({\vec {y}}_{0}+t\,{\hat {w}}\right)\right\rangle \\&=\ldots \\&=t^{2}-2t\,\left\langle y_{D}-y_{0},{\hat {w}}\right\rangle \end{aligned}}$

We find the minimum of this function at $t=0$, so we find that $\left\langle {\vec {y}}_{D}-{\vec {y}}_{0},{\hat {w}}\right\rangle =0$ and furthermore $\left\langle {\vec {y}}_{D}-{\vec {y}}_{0},{\vec {y}}\right\rangle =0$ for all ${\vec {y}}\in W$.

Punchline

Theorem. Let $V$ be an inner product space and let $W\subset V$ be a subspace of $V$. Also, let ${\vec {v}}$ be any vector in $V$. Then, ${\vec {w}}_{0}$ minimizes $\left\|{\vec {v}}-{\vec {w}}\right\|$ over all ${\vec {w}}\in W$ if and only if ${\vec {v}}-{\vec {w}}_{0}\perp W$.

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

quod erat demonstrandum

Finding ${\vec {w}}_{0}$

How do we find ${\vec {w}}_{0}$ (or in the special case ${\vec {y}}_{0}$)?

${\vec {w}}_{0}$ is the orthogonal projection of ${\vec {v}}$ onto the vector space $W$.

Let $\left\{{\hat {e}}_{1},{\hat {e}}_{2},\ldots ,{\hat {e}}_{n}\right\}$ be an orthonormal basis for $W$. Then

$\mathrm {proj} _{W}\left({\vec {v}}\right)=\sum _{k=1}^{n}\left\langle {\vec {v}},{\hat {e}}_{k}\right\rangle \,{\hat {e}}_{k}$