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 $(1,1),(2,2),(3,\frac{3}{2}),(4,\frac{3}{2})$:

Hence the coefficients to our control points $a_0$ and $a_1$ are

$A=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\\ 1& 4\end{array}\right]$

and our values are

$\overrightarrow{b}=\left[\begin{array}{c}1\\ 2\\ \frac{3}{2}\\ \frac{3}{2}\end{array}\right]$

We compute $A^{T}A=\left[\begin{array}{cc}4& 10\\ 10& 30\end{array}\right]$ and solve the following for $\overrightarrow{x}=\left[\begin{array}{c}{a}_0\\ a_1\end{array}\right]$:

$A^{T}A\overrightarrow{x}=A^T\overrightarrow{b}$

$\overrightarrow{x}=\left[\begin{array}{c}\frac{5}{4}\\ \frac{1}{10}\end{array}\right]$

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

General Case

for $f\in {\mathbb{ℝ}}^n$, $\mathrm{\Pi }$ is a subspace spanned by ${\varphi }_1,{\varphi }_2,\dots ,{\varphi }_n$, where $\varphi$'s are linearly independent.

We wish to approximate $f\in {\mathbb{ℝ}}^n$ by $p\in \mathrm{\Pi }$. We do so by minimizing the value of ${\Vert f-p\Vert }_2^2$ for all $p\in \mathrm{\Pi }$. This is called the best least squares fit

$p$ is just the projection of $f$ onto $\mathrm{\Pi }$.

Normal equations are:

$A^{T}A=\left[\begin{array}{cccc}⟨{\varphi }_1,{\varphi }_1⟩& ⟨{\varphi }_1,{\varphi }_2⟩& \dots & ⟨{\varphi }_1,{\varphi }_n⟩\\ ⟨{\varphi }_2,{\varphi }_1⟩& ⟨{\varphi }_2,{\varphi }_2⟩& \dots & ⟨{\varphi }_2,{\varphi }_n⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{\varphi }_n,{\varphi }_1⟩& ⟨{\varphi }_n,{\varphi }_2⟩& \dots & ⟨{\varphi }_n,{\varphi }_n⟩\end{array}\right]$

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

Theorem. If $⟨f-p,q⟩=0$ for all $q\in \mathrm{\Pi }$, then $p$ is the minimizer for ${\Vert f-p\Vert }_2^2$.

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

Take $q\ne p$ and compute

$\begin{array}{rl}{\Vert f-q\Vert }^2& =⟨f-q,f-q⟩=⟨f-p+p-q,f-p+p-q⟩\\ & ={\Vert f-p\Vert }^2+⟨f-p,p-q⟩+⟨p-q,f-p⟩+{\Vert p-q\Vert }^2\\ & ={\Vert f-p\Vert }^2+{\Vert p-q\Vert }^2+\underset{0}{\underbrace{2⟨f-p,p-q⟩}}\\ & ={\Vert f-p\Vert }^2+{\Vert p-q\Vert }^2\end{array}$

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

quod erat demonstrandum

Special Case

Let $\mathrm{\Pi }$ be spanned by an orthonormal basis ${\psi }_1,\dots ,{\psi }_k$, and let ${\mathrm{\Pi }}^{\perp }$ be spanned by an orthonormal basis ${\psi }_{k+1},\dots ,{\psi }_n$. Thus ${\mathbb{ℝ}}^n=\mathrm{\Pi }\oplus {\mathrm{\Pi }}^{\perp }$.

Now $f\in {\mathbb{ℝ}}^n$ is given by $f=\sum _{i=1}^n⟨f,{\psi }_i⟩{\psi }_i$.

To find the projection, we just take the components that are members of $\mathrm{\Pi }$:

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{\mathrm{\Pi }}(f)=\sum _{i=1}^k⟨f,{\psi }_i⟩{\psi }_i$