Projection

Definition

Let $S$ be a subspace of ${\mathbb{R}}^m$

$$pro{j}_S(b)=\underset{p\in S}{\mathrm{argmin}}\Vert b-p\Vert$$

Question

• Does there always exist a minimum?
• Is $pro{j}_S(b)$ unique?

One-dimensional case

$S$ is a one dimensional subspace in ${\mathbb{R}}^n$ This means: $S=\{\lambda a|\lambda \in \mathbb{R}\}=C(a)$ and $a\in {\mathbb{R}}^m$ with $a\ne 0$ We know $b\in {\mathbb{R}}^m$ Hypothesis: $pro{j}_S(b)={\lambda }^{\ast }a$ with ${\lambda }^{\ast }\in \mathbb{R}$ $b-pro{j}_S(b)$ is orthogonal to $pro{j}_S(b)$ (See proof below)

Lemma 5.2.2

${\text{proj}}_{C(a)}(b)={\lambda }^{\ast }a$ ${\lambda }^{\ast }=\frac{a^{\top }b}{\Vert a{\Vert }^2}$ (see the proof below) ${\text{proj}}_S(b)=\frac{a^{\top }b}{\Vert a{\Vert }^2}a=\frac{a^{\top }b}{a^{\top }a}a=\frac{a{a}^{\top }}{a^{\top }a}b$

Proof: $b-pro{j}_S(b)$ is orthogonal to $pro{j}_S(b)$ $⟺a^{\top }\left(b-\frac{a^{\top }b}{a^{\top }a}a\right)=a^{\top }b-\frac{a^{\top }b}{a^{\top }a}{a}^{\top }a=a^{\top }b-a^{\top }b=0$

Proof: Lemma 5.2.2 $\Vert b-p{\Vert }^2=(b-p{)}^{\top }(b-p)=b^{\top }b-2b^{\top }p+p^{\top }p=b^{\top }b-2b^{\top }\lambda a+{\lambda }^2{a}^{\top }a=g(\lambda )$ (recall that $a^{\top }b=b^{\top }a$) $g^{\prime }(\lambda )=-2a^{\top }b+2\lambda a^{\top }a=0⟺\lambda =\frac{a^{\top }b}{a^{\top }a}$

If $S=\{a\cdot \lambda |\lambda \in \mathbb{R}\}$ and $a\in {\mathbb{R}}^m\setminus \{0\}$, then ${\text{proj}}_S(b)=\frac{1}{\Vert a{\Vert }^2}a\cdot a^{\top }b$

General case

Consider $S\subseteq {\mathbb{R}}^m$ Let $a_1,\dots ,a_n\in {\mathbb{R}}^m$ Let $S=\left\{{\sum }_{i=1}^n{a}_i{\lambda }_i|{\lambda }_1,\dots ,{\lambda }_n\in \mathbb{R}\right\}=\{A\cdot \lambda \}|\lambda \in {\mathbb{R}}^n$ $A=[a_1|a_2|\dots |a_n]$

Lemma 5.2.3

The projection of $b\in {\mathbb{R}}^m$ on $S=C(A)$ is a vector $A\cdot \hat{x},\hat{x}\in {\mathbb{R}}^n$ with $A^{\top }A\hat{x}=A^{\top }b$

• Proof

Lemma 5.2.4

Let $A\in {\mathbb{R}}^{m\times n}$ then $A^{\top }A$ is invertible if and only if columns of $A$ are linear independent

Proof: $N(A^{\top }A)=N(A)$ $A^{\top }A\in {\mathbb{R}}^{n\times n}$ $A^{\top }A$ invertible $⟺N(A^{\top }A)=\{0\}$ $⟺N(A)=\{0\}$ $⟹$ columns of $A$ are linear independent

Link to original

Since $A^{\top }A$ is invertible, according to Lemma 5.2.3, ${\text{proj}}_S(b)=A\hat{x}=A(A^{\top }A{)}^{-1}{A}^{\top }b$

Theorem 5.2.5

$${\text{proj}}_S(b)=Pb\text{ with }P=A(A^{\top }A{)}^{-1}{A}^{\top }\in {\mathbb{R}}^{m\times m}$$

Remark $PA=A(A^{\top }A{)}^{-1}{A}^{\top }A=A(A^{\top }A{)}^{-1}(A^{\top }A)=A$

Least Square (Data Fitting)

When $\Vert A\hat{x}-b{\Vert }^2$ is minimal (OR we can write $\Vert b-{\text{proj}}_S(b){\Vert }^2$) $\hat{x}$ is the least square solution $A^{\top }A\hat{x}=A^{\top }b$ $\hat{x}=(A^{\top }A{)}^{-1}{A}^{\top }b$

Application: Linear Regression

Data: $(t_k,b_k)$ where $k=1,\dots ,m$

We want to find $min\left\{{\sum }_{k=1}^m(b_k-{\alpha }_0-{\alpha }_1{t}_k{)}^2|{\alpha }_0,{\alpha }_1=\mathbb{R}\right\}$ $\underset{x}{\min }\Vert Ax-b{\Vert }^2$ Solution:

$$\left[\begin{array}{c}{\alpha }_0\\ {\alpha }_1\end{array}\right]=(A^{\top }A{)}^{-1}{A}^{\top }b={\left[\begin{array}{cc}m& {\sum }_{k=1}^m{t}_k\\ {\sum }_{k=1}^m{t}_k& {\sum }_{k=1}^m{t}_k^2\end{array}\right]}^{-1}\left[\begin{array}{c}{\sum }_{k=1}^m{b}_k\\ {\sum }_{k=1}^m{b}_k{t}_k\end{array}\right]$$

We can extend this method to cubic, quadratic…