MATH 323 Lecture 23

« previous | Tuesday, November 20, 2012 | next »

Least Squares Problem

given a $m\times n$ matrix $A$ with rank $n$, the least-squares solution to the equation $A\overrightarrow{x}=\overrightarrow{b}$ is given by

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

and has the unique solution

$\hat{x}=(A^{T}A{)}^{-1}{A}^T\overrightarrow{b}$

the vector $\overrightarrow{p}\in A\overrightarrow{x}$ in the range of $A$ is closest to $\overrightarrow{b}$.

Assume the columns of $A$ constitute an orthonormal basis in $R(A)$.

Theorem 5.5.6

If the column vectors of $A$ form an orthonormal set of vectors in ${\mathbb{ℝ}}^m$, then $A^{T}A=I$ and the solution to the least squares problem is

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

Proof

We need to show that $A^{T}A=I$.

If $A^{T}A=(c_{ij})$, then $c_{ij}={\overrightarrow{a}}_i\cdot {\overrightarrow{a}}_j={\delta }_{ij}=\{\begin{array}{ll}1& i=j\\ 0& \text{otherwise}\end{array}$

Therefore, the diagonal entries for

$i=j$

will be 1, and all other matrix cells will be 0.

Q.E.D.

Theorem 5.5.7

Let $S$ be a subspace in $(V,⟨\cdot ,\cdot ⟩)$ and let $x\in V$.

Let $\dim S=n$ and $\{x_1,\dots ,x_n\}$ be an orthonormal basis for $S$.

If $p=\sum _{i=1}^n{c}_i{x}_i$ where $c_i=⟨x,x_i$ for all $i$, then $p-x\in S^{\perp }$.

Proof

Show that $(p-x)\perp x_i$ for any $i$:

$\begin{array}{rl}⟨p-x,x_i⟩& =⟨\sum _{j=1}^n{c}_j{x}_j,x_i⟩-⟨x,x_i⟩\\ & =\sum _{j=1}^n{c}_j⟨x_j,x_i⟩-⟨x,x_i⟩\\ & =\sum _{j=1}^n{c}_j{\delta }_{ij}-⟨x,x_i⟩\\ & =c_i⟨x_i,x_i⟩-c_i\\ & =c_i-c_i\\ & =0\end{array}$

Theorem 5.5.8

Under hypothesis of #Theorem 5.5.7, $p$ is the element of $S$ that is closest to $x$. That is, $\Vert y-x\Vert >\Vert p-x\Vert$ for all $y\ne p$ in $S$.

Corollary 5.5.9

Let $S$ be a nonzero subspace in ${\mathbb{ℝ}}^m$ and let $p\in {\mathbb{ℝ}}^m$.

If \{\vec{u}_1, \ldots, \vec{u}_k \} is an orthonormal basis for $S$ and $U=({\overrightarrow{u}}_1,\dots ,{\overrightarrow{u}}_k)$, then the projection $\overrightarrow{p}$ of $\overrightarrow{b}$ onto $S$ is given by \vec{p} = UU^T \vec{b}</math>

Proof

$\overrightarrow{p}=\sum _{i=1}^k{c}_i{\overrightarrow{u}}_i=U\overrightarrow{c}=U{U}^T\overrightarrow{b}$

$\overrightarrow{c}=\left(\begin{array}{c}{\overrightarrow{u}}_1^T\overrightarrow{b}\\ ⋮\\ {\overrightarrow{u}}_k^T\overrightarrow{b}\end{array}\right)=U^T\overrightarrow{b}$

Let $P=U{U}^T$ be the projection matrix for $S$.

Going back to the formula for the least squares solution, $\hat{x}=(A^{T}A{)}^{-1}{A}^T\overrightarrow{b}$, $P=(A^{T}A{)}^{-1}{A}^T$

$P$ is unique to $S$ regardless of basis used. However, $P=U{U}^T$ can only be used for orthonormal bases; other calculations must use $P=(A^{T}A{)}^{-1}{A}^T$

Example

Find best least squares approximation of $e^x$ on [0,1] by a linear function (subspace of C[0,1])

• Space: C[0,1]
• Inner product: $⟨f,g⟩=\underset{0}{\overset{1}{\int }}f(x)g(x)\mathrm{d}x$
• Subsace: $S=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{1,x\}$ (linear functions)

Find $a$ such that $(x-a)\perp 1$:

$⟨1,x-a⟩=\underset{0}{\overset{1}{\int }}(x-a)\mathrm{d}x=\frac{1}{2}-a=0$

Therefore $a=\frac{1}{2}$, and $\{1,x-\frac{1}{2}\}$ forms an orthogonal basis for $S$.

Find orthonormal basis for $S$:

$\begin{array}{rl}\Vert x-\frac{1}{2}\Vert & =\sqrt{\underset{0}{\overset{1}{\int }}{(x-\frac{1}{2})}^2\mathrm{d}x}=\frac{1}{\sqrt{12}}\\ \Vert 1\Vert & =1\\ u_1& =1\\ u_2& =\frac{x-\frac{1}{2}}{\Vert x-\frac{1}{2}\Vert }=\sqrt{12}(x-\frac{1}{2})\end{array}$

Therefore $\{1,\sqrt{12}(x-\frac{1}{2})\}$ forms an orthonormal basis for $S$

Find least squares approximation:

$\begin{array}{rl}p& =c_1{u}_1+c_2{u}_2\\ c_1& =⟨{\mathrm{e}}^x,u_1⟩=\underset{0}{\overset{1}{\int }}{\mathrm{e}}^x\mathrm{d}x=\mathrm{e}-1\\ c_2& =⟨{\mathrm{e}}^x,u_2⟩=\underset{0}{\overset{1}{\int }}{\mathrm{e}}^x(x-\frac{1}{2})\mathrm{d}x=\sqrt{3}(3-e)\\ p& =(\mathrm{e}-1)\cdot 1+(\sqrt{3}(\mathrm{e}-3))\cdot (\sqrt{12}(x-\frac{1}{2}))\\ & =(4\mathrm{e}-10)+(6(3-\mathrm{e}))x\end{array}$

Fourier Approximation

$\begin{array}{rl}{r}_k& =\sqrt{a_k^2+b_k^2}\\ {\theta }_k& =\arctan \left(\frac{b_k}{a_k}\right)\\ a_k\cos kx+b_k\sin kx& =r_k\cos kx-{\theta }_k\end{array}$

The last formula is the equation for harmonic motion.

Gram-Schmidt Process

For $V,⟨\cdot ,\cdot ⟩$, and $\{x_1,\dots ,x_n\}$ basis in $V$,

How do we obtain $\{u_1,\dots ,u_n\}$, an orthonormal basis for $S$ so that $\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x_1,\dots ,x_n\}=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{u_1,\dots ,u_n\}$?

$\begin{array}{rl}{u}_1& =\frac{x_1}{\Vert x_1\Vert }\\ \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x_1\}& =\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{u_1\}=V_1\\ p_1& ={\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V_1}(x_2)=⟨x_2,u_1⟩\cdot u_1\\ & x_2-p_1\perp V_1\\ u_2& =\frac{x_2-p_1}{\Vert x_2-p_1\Vert }\\ \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x_1,x_2\}& =\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{u_1,u_2\}=V_2\\ p_2& ={\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{V_1}(x_3)=⟨x_3,u_2⟩\cdot u_2\\ & x_3-p_2\perp V_2\\ & \dots \end{array}$

Theorem 5.6.1

Let $\{x_1,\dots ,x_n\}$ be a basis for $V,⟨\cdot ,\cdot ⟩$. Let $u_1=\frac{x_1}{\Vert x_1\Vert }$ and define $u_2,\dots ,u_n$ recursively by

$u_{k+1}=\frac{x_{k+1}-p_k}{\Vert x_{k+1}-p_k\Vert }$

Where $p_k=⟨x_{k+1},u_1⟩u_1+⟨x_{k+1},u_2⟩u_2+\dots +⟨x_{k+1},u_k⟩u_k$ is the projection of $x_{k+1}$ onto $v_k=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(u_1,\dots ,u_k)=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(x_1,\dots ,x_k)$.

The set $\{u_1,\dots ,u_n\}$ is an orthonormal basis for $V$.