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{\vec {x}}={\vec {b}}$ is given by

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

and has the unique solution

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

the vector ${\vec {p}}\in A{\vec {x}}$ in the range of $A$ is closest to ${\vec {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 {R} ^{m}$, then $A^{T}A=I$ and the solution to the least squares problem is

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

Proof

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

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

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,\langle \cdot ,\cdot \rangle )$ and let $x\in V$.

Let $\dim {S}=n$ and $\{x_{1},\ldots ,x_{n}\}$ be an orthonormal basis for $S$.

If $p=\sum _{i=1}^{n}c_{i}\,x_{i}$ where $c_{i}=\langle x,x_{i}$ for all $i$, then $p-x\in S^{\perp }$.

Proof

Show that $(p-x)\perp x_{i}$ for any $i$:

${\begin{aligned}\langle p-x,x_{i}\rangle &=\left\langle \sum _{j=1}^{n}c_{j}\,x_{j},x_{i}\right\rangle -\langle x,x_{i}\rangle \\&=\sum _{j=1}^{n}c_{j}\langle x_{j},x_{i}\rangle -\langle x,x_{i}\rangle \\&=\sum _{j=1}^{n}c_{j}\delta _{ij}-\langle x,x_{i}\rangle \\&=c_{i}\langle x_{i},x_{i}\rangle -c_{i}\\&=c_{i}-c_{i}\\&=0\end{aligned}}$

Theorem 5.5.8

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

Corollary 5.5.9

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

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

Proof

${\vec {p}}=\sum _{i=1}^{k}c_{i}\,{\vec {u}}_{i}=U{\vec {c}}=UU^{T}{\vec {b}}$

${\vec {c}}={\begin{pmatrix}{\vec {u}}_{1}^{T}{\vec {b}}\\\vdots \\{\vec {u}}_{k}^{T}{\vec {b}}\end{pmatrix}}=U^{T}{\vec {b}}$

Let $P=UU^{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}{\vec {b}}$, $P=(A^{T}A)^{-1}A^{T}$

$P$ is unique to $S$ regardless of basis used. However, $P=UU^{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: $\langle f,g\rangle =\int _{0}^{1}f(x)\,g(x)\,\mathrm {d} x$
• Subsace: $S=\mathrm {Span} \{1,x\}$ (linear functions)

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

$\langle 1,x-a\rangle =\int _{0}^{1}(x-a)\,\mathrm {d} x={\frac {1}{2}}-a=0$

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

Find orthonormal basis for $S$:

${\begin{aligned}\left\|x-{\frac {1}{2}}\right\|&={\sqrt {\int _{0}^{1}\left(x-{\frac {1}{2}}\right)^{2}\,\mathrm {d} x}}={\frac {1}{\sqrt {12}}}\\\|1\|&=1\\u_{1}&=1\\u_{2}&={\frac {x-{\frac {1}{2}}}{\left\|x-{\frac {1}{2}}\right\|}}={\sqrt {12}}\left(x-{\frac {1}{2}}\right)\end{aligned}}$

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

Find least squares approximation:

${\begin{aligned}p&=c_{1}\,u_{1}+c_{2}\,u_{2}\\c_{1}&=\langle \mathrm {e} ^{x},u_{1}\rangle =\int _{0}^{1}\mathrm {e} ^{x}\,\mathrm {d} x=\mathrm {e} -1\\c_{2}&=\langle \mathrm {e} ^{x},u_{2}\rangle =\int _{0}^{1}\mathrm {e} ^{x}\,\left(x-{\frac {1}{2}}\right)\,\mathrm {d} x={\sqrt {3}}(3-e)\\p&=(\mathrm {e} -1)\cdot 1+({\sqrt {3}}(\mathrm {e} -3))\cdot ({\sqrt {12}}(x-{\tfrac {1}{2}}))\\&=(4\mathrm {e} -10)+(6(3-\mathrm {e} ))\,x\end{aligned}}$

Fourier Approximation

${\begin{aligned}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{aligned}}$

The last formula is the equation for harmonic motion.

Gram-Schmidt Process

For $V,\langle \cdot ,\cdot \rangle$, and $\{x_{1},\ldots ,x_{n}\}$ basis in $V$,

How do we obtain $\{u_{1},\ldots ,u_{n}\}$, an orthonormal basis for $S$ so that $\mathrm {Span} \{x_{1},\ldots ,x_{n}\}=\mathrm {Span} \{u_{1},\ldots ,u_{n}\}$?

${\begin{aligned}u_{1}&={\frac {x_{1}}{\|x_{1}\|}}\\\mathrm {Span} \{x_{1}\}&=\mathrm {Span} \{u_{1}\}=V_{1}\\p_{1}&=\mathrm {proj} _{V_{1}}(x_{2})=\langle x_{2},u_{1}\rangle \cdot u_{1}\\&x_{2}-p_{1}\perp V_{1}\\u_{2}&={\frac {x_{2}-p_{1}}{\|x_{2}-p_{1}\|}}\\\mathrm {Span} \{x_{1},x_{2}\}&=\mathrm {Span} \{u_{1},u_{2}\}=V_{2}\\p_{2}&=\mathrm {proj} _{V_{1}}(x_{3})=\langle x_{3},u_{2}\rangle \cdot u_{2}\\&x_{3}-p_{2}\perp V_{2}\\&\ldots \end{aligned}}$

Theorem 5.6.1

Let $\{x_{1},\ldots ,x_{n}\}$ be a basis for $V,\langle \cdot ,\cdot \rangle$. Let $u_{1}={\tfrac {x_{1}}{\|x_{1}\|}}$ and define $u_{2},\ldots ,u_{n}$ recursively by

$u_{k+1}={\frac {x_{k+1}-p_{k}}{\|x_{k+1}-p_{k}\|}}$

Where $p_{k}=\langle x_{k+1},u_{1}\rangle u_{1}+\langle x_{k+1},u_{2}\rangle u_{2}+\dots +\langle x_{k+1},u_{k}\rangle u_{k}$ is the projection of $x_{k+1}$ onto $v_{k}=\mathrm {Span} (u_{1},\ldots ,u_{k})=\mathrm {Span} (x_{1},\ldots ,x_{k})$.

The set $\{u_{1},\ldots ,u_{n}\}$ is an orthonormal basis for $V$.