MATH 417 Lecture 24

« previous | Thursday, April 17, 2014 | next »

Suppose we want to find a linear approximation $f(x)=a_{0}+a_{1}\,x$ for the points $\left(1,1\right),\left(2,2\right),\left(3,{\frac {3}{2}}\right),\left(4,{\frac {3}{2}}\right)$ :

Hence the coefficients to our control points $a_{0}$ and $a_{1}$ are

$A={\begin{bmatrix}1&1\\1&2\\1&3\\1&4\end{bmatrix}}$

and our values are

${\vec {b}}={\begin{bmatrix}1\\2\\{\frac {3}{2}}\\{\frac {3}{2}}\end{bmatrix}}$

We compute $A^{T}\,A={\begin{bmatrix}4&10\\10&30\end{bmatrix}}$ and solve the following for ${\vec {x}}={\begin{bmatrix}a_{0}\\a_{1}\end{bmatrix}}$ :

$A^{T}\,A\,{\vec {x}}=A^{T}\,{\vec {b}}$

${\vec {x}}={\begin{bmatrix}{\frac {5}{4}}\\{\frac {1}{10}}\end{bmatrix}}$

Hence our equation is: $f(x)={\frac {5}{4}}+{\frac {1}{10}}\,x$

General Case

for $f\in \mathbb {R} ^{n}$ , $\Pi$ is a subspace spanned by $\phi _{1},\phi _{2},\ldots ,\phi _{n}$ , where $\phi$ 's are linearly independent.

We wish to approximate $f\in \mathbb {R} ^{n}$ by $p\in \Pi$ . We do so by minimizing the value of $\left\|f-p\right\|_{2}^{2}$ for all $p\in \Pi$ . This is called the best least squares fit

p

is just the projection of

f

onto

\Pi

.

Normal equations are:

$A^{T}\,A={\begin{bmatrix}\left\langle \phi _{1},\phi _{1}\right\rangle &\left\langle \phi _{1},\phi _{2}\right\rangle &\dots &\left\langle \phi _{1},\phi _{n}\right\rangle \\\left\langle \phi _{2},\phi _{1}\right\rangle &\left\langle \phi _{2},\phi _{2}\right\rangle &\dots &\left\langle \phi _{2},\phi _{n}\right\rangle \\\vdots &\vdots &\ddots &\vdots \\\left\langle \phi _{n},\phi _{1}\right\rangle &\left\langle \phi _{n},\phi _{2}\right\rangle &\dots &\left\langle \phi _{n},\phi _{n}\right\rangle \end{bmatrix}}$

Residual (or rejection) belongs to the subspace perpendicular to $\Pi$ , or $\Pi ^{\perp }$ .

Theorem. If $\left\langle f-p,q\right\rangle =0$ for all $q\in \Pi$ , then $p$ is the minimizer for $\left\|f-p\right\|_{2}^{2}$ .

Proof. If $p$ is the projection of $f$ onto a subspace, then $f-p$ is the shortest vector from $\Pi$ to $f$ . The shortest vector from $\Pi$ to $p$ is orthogonal to $\Pi$ (otherwise $\left\|f-p\right\|$ would not be minimized). Hence $p-q$ is orthogonal to $f-p$ .

Take $q\neq p$ and compute

${\begin{aligned}\left\|f-q\right\|^{2}&=\left\langle f-q,f-q\right\rangle =\left\langle f-p+p-q,f-p+p-q\right\rangle \\&=\left\|f-p\right\|^{2}+\left\langle f-p,p-q\right\rangle +\left\langle p-q,f-p\right\rangle +\left\|p-q\right\|^{2}\\&=\left\|f-p\right\|^{2}+\left\|p-q\right\|^{2}+\underbrace {2\left\langle f-p,p-q\right\rangle } _{0}\\&=\left\|f-p\right\|^{2}+\left\|p-q\right\|^{2}\end{aligned}}$

Theus $p=q$ minimizes the value of $\left\|p-q\right\|^{2}$ , and thus $\left\|f-q\right\|^{2}=\left\|f-p\right\|^{2}$

quod erat demonstrandum

Special Case

Let $\Pi$ be spanned by an orthonormal basis $\psi _{1},\ldots ,\psi _{k}$ , and let $\Pi ^{\perp }$ be spanned by an orthonormal basis $\psi _{k+1},\ldots ,\psi _{n}$ . Thus $\mathbb {R} ^{n}=\Pi \oplus \Pi ^{\perp }$ .