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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w}_0} minimizes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\| \vec{v} - \vec{w} \right\|} over all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w} \in W} if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{v} - \vec{w}_0 \perp W} .

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

quod erat demonstrandum

Finding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w}_0}

How do we find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w}_0} (or in the special case Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{y}_0} )?

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{w}_0} is the orthogonal projection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{v}} onto the vector space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} .

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \hat{e}_1, \hat{e}_2, \ldots, \hat{e}_n \right\}} be an orthonormal basis for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W} . Then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{proj}_W \left( \vec{v} \right) = \sum_{k=1}^n \left\langle \vec{v}, \hat{e}_k \right\rangle \, \hat{e}_k}