MATH 323 Lecture 21

« previous | Thursday, November 8, 2012 | next »

Least Squares Problem

Given subspace $S\subset \mathbb{ℝ}$ and a vector $\overrightarrow{v}\in ̸S$, find the closest approximation $\overrightarrow{p}\in S$. $\overrightarrow{p}$ is a vector projection, and $\Vert \overrightarrow{p}\Vert$ is the α-scalar projection.

When represented by $A\overrightarrow{x}=\overrightarrow{b}$, $S=R(A)$ is the column space of $A$, and $\hat{x}$ is the vector such that $\overrightarrow{p}=A\hat{x}$. We get $r(\hat{x})=\overrightarrow{b}-\overrightarrow{p}=\overrightarrow{b}-A\hat{x}$ is the residual vector.

Normal Equation

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

Theorem 5.3.2

$A$ is a $m\times n$ matrix of rank $n$ (same rank as number of columns). Then the normal equation $A^{T}A\overrightarrow{x}=\overrightarrow{b}$ has a unique solution given by

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

And $\hat{x}$ is the unique least squares solution to the sysetm $A\overrightarrow{x}=\overrightarrow{b}$.

Proof

Based on premise that $A^{T}A$ is nonsingular.

Assume we have some vector $A^{T}A\overrightarrow{z}=\overrightarrow{0}$. For $A^{T}A$ to be nonsingular, $z=\overrightarrow{0}$ must be the only solution.

We know that

• $A\overrightarrow{z}\in N(A^T)$
• $A\overrightarrow{z}\in R(A)$
• and $R(A)\perp N(A^T)$

Therefore

$A\overrightarrow{z}\in (R(A)\cap N(A^T))=\{\overrightarrow{0}\}$

.

Q.E.D.

Corollary

We already know that $\overrightarrow{p}=A\hat{x}$, and $\hat{x}=(A^{T}A{)}^{-1}{A}^T\overrightarrow{b}$, so

$\overrightarrow{p}=\underset{P}{\underbrace{A(A^{T}A{)}^{-1}{A}^T}}\overrightarrow{b}$

The projection matrix $P$ is interesting because $P^2=P$:

$P^2=A\cancel{(A^{T}A{)}^{-1}}\cancel{A^{T}A}(A^{T}A{)}^{-1}{A}^T=A(A^{T}A{)}^{-1}{A}^T$

Example

Overdetermined system

$\begin{array}{rl}{x}_1+x_2& =3\\ -2x_1+3x_2& =1\\ 2x_1-x_2& =2\end{array}$

$\begin{array}{rl}A& =\left(\begin{array}{cc}1& 1\\ -2& 3\\ 2& -1\end{array}\right)\\ A^T& =\left(\begin{array}{ccc}1& -2& 2\\ 1& 3& -1\end{array}\right)\\ \overrightarrow{b}& =\left(\begin{array}{c}3\\ 1\\ 2\end{array}\right)\end{array}$

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

$\hat{x}=\left(\begin{array}{c}\frac{81}{50}\\ \frac{71}{50}\end{array}\right)$

Regression

Given a set of measurements $y_1,\dots ,y_n$ at points $x_1,\dots ,x_n$, each set of values defines a point at $(x_i,y_i)$.

Linear Regression

Find equation such that $y=c_0+c_{1}x$ that approximates the system of equations

$\left[\begin{array}{cc}1& x_1\\ 1& x_2\\ ⋮& ⋮\\ 1& x_n\end{array}\right]\left[\begin{array}{c}{c}_0\\ c_1\end{array}\right]=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$

Solution for $A\overrightarrow{c}=\overrightarrow{y}$ is given by $A^{T}A\overrightarrow{c}=A^T\overrightarrow{y}$

Inner Product Spaces

Vector space $V$. Suppose we have a function such that for all $x,y\in V$, the inner product of $x,y$ (notation $⟨x,y⟩$) is a real number.

We want to have the following properties:

1. $⟨x,x⟩\ge 0$ and is equal to 0 iff $x=0$
2. $⟨x,y⟩=⟨y,x⟩$ (commutativity)
3. $⟨\alpha x+\beta y,z⟩=\alpha ⟨x,z⟩+\beta ⟨y,z⟩$ and the same applies for the second component.

Example 1

${\mathbb{ℝ}}^n$, $⟨\overrightarrow{x},\overrightarrow{y}⟩=\overrightarrow{x}\cdot \overrightarrow{y}$ is the scalar product.

Given $\overrightarrow{w}$ weights such that $w_i\ge 0\mathrm{\forall }{w}_i\in \overrightarrow{w}$,

${⟨\overrightarrow{x},\overrightarrow{y}⟩}_{\overrightarrow{w}}=\sum _{i=1}^n{w}_i{x}_i{y}_i$

Example 2

Given two matrices $A,B\in M_{m,n}(\mathbb{ℝ})$, let $⟨A,B⟩=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{b}_{ij}$.

Example 3

Given two functions $f,g\in C[a,b]$, let $⟨f,g⟩=\underset{a}{\overset{b}{\int }}f(x)g(x)\mathrm{d}x$

1. $⟨f,f⟩=\underset{a}{\overset{b}{\int }}{f}^2(x)\mathrm{d}x\ge 0$ and $⟨f,f⟩=\underset{a}{\overset{b}{\int }}{f}^2(x)\mathrm{d}x=0⟺f\equiv 0$
2. …

Properties

Given a vector space $V$ and an inner product function $⟨\cdot ,\cdot ⟩$

We can redefine:

• length / norm: $\Vert V\Vert =\sqrt{⟨v,v⟩}$
• Orthogonality: $u\perp v⟺⟨u,v⟩=0$
• Scalar projection: $\alpha =\frac{⟨u,v⟩}{\Vert v\Vert }$
• Vector projection: $p=\alpha \cdot \left(\frac{1}{\Vert v\Vert }v\right)=\frac{⟨u,v⟩}{⟨v,v⟩}v$

Theorem 5.4.1

The Pythagorean Law

If $u\perp v$, then $\Vert u+v{\Vert }^2=\Vert u{\Vert }^2+\Vert v{\Vert }^2$

Proof

$\begin{array}{rl}\Vert u+v{\Vert }^2& =⟨u+v,u+v⟩\\ & =⟨u,u⟩+⟨u,v⟩+⟨v,u⟩+⟨v,v⟩\\ & =\Vert u{\Vert }^2+0+0+\Vert v{\Vert }^2\end{array}$

Orthogonality of Functions

$1\perp x$, where the inner product is defined as $⟨f,g⟩=\underset{-1}{\overset{1}{\int }}f(x)g(x)\mathrm{d}x$

$⟨1,x⟩=\underset{-1}{\overset{1}{\int }}1\cdot x\mathrm{d}x=0$

Theorem 5.4.2

The Cauchy-Schwarz Inequality

$\left|⟨u,v⟩\right|\le \Vert u\Vert \Vert v\Vert$

Holds iff $u$ and $v$ are linearly dependent.