Projections onto Subspaces

June 2, 2019

Projections

\begin{tikzpicture}[scale=1.0544]\small
\begin{axis}[axis line style=gray,
samples=120,
width=6.0cm,height=6.4cm,
xmin=-1.5, xmax=3.5,
ymin=-1.5, ymax=3.5,
%restrict y to domain=-2:2,
ytick={-1,0,1,2,3},
xtick={-1,0,1,2,3},
axis equal,
axis x line=center,
axis y line=center,
xlabel=$x$,ylabel=$y$]
\addplot[->,color = {rgb:red,181;green,23;blue,23}, line width = 1pt] coordinates
{(0,0) (3,1.5)};
\addplot[->,color = {rgb:red,16;green,133;blue,152}, line width = 1pt] coordinates {(0,0) (1,2)};
%p
\addplot[->,color = {rgb:red,16;green,133;blue,152}, line width = 1pt] coordinates {(0,0) (1.6,0.8)};
%e
\addplot[dashed, ->,color = {rgb:red,66;green,177;blue,8}, line width = 1pt] coordinates {(1.6,0.8) (1,2)};
% red vector label
\addplot[color = {rgb:red,181;green,23;blue,23}] coordinates {(3,1.8)} node{$\mathbf a$};
% blue vector label
\addplot[color = {rgb:red,16;green,133;blue,152}] coordinates {(1,2.3)} node{$\mathbf b$};
% dashed vector label
\addplot[color = {rgb:red,66;green,177;blue,8}] coordinates {(1.5,1.5)} node{$\mathbf e$};
% p vector label
\addplot[color = {rgb:red,16;green,133;blue,152}] coordinates {(1.5,0.4)} node{$\mathbf p$};
%zero node
\path (axis cs:0,0) node [anchor=north west,yshift=-0.07cm] {0};
\end{axis}
\end{tikzpicture} — Figure 1. Vector p projecting into vector a; resulting in p=xa; e=b-p

Let’s start with an example. On Figure 1, We have $\mathbf a$ and $\mathbf b$ both are one dimensional line in $\mathbb R^2$ . We project $\mathbf b$ into $\mathbf a$ , and obtain its projected vector $\mathbf p=x\mathbf a$ where $x$ (fraction here) is a constant, and the distance between the original and projected one $\mathbf e=\mathbf b - \mathbf p$ . Since $\mathbf a$ and $\mathbf e$ is orthogonal, we have the following equation:

$\begin{align} \mathbf a^\top\mathbf e&=0\tag{1}\\ \mathbf a^\top(\mathbf b-\mathbf p)&=0\\ \mathbf a^\top(\mathbf b-x\mathbf a)&=0\\ \end{align}$

Solving it we get $\displaystyle x=\frac{\mathbf a^\top \mathbf b}{\mathbf a^\top \mathbf a}$ , and thus (x is constant so we can put it left or right)

$\mathbf p=\mathbf a \frac{\mathbf a^\top \mathbf b}{\mathbf a^\top \mathbf a}\tag{2}$

Right now let’s separate $\mathbf {a\ b}$ in eq. (2). Let $\displaystyle P=\frac{\mathbf a \mathbf a^\top}{\mathbf a^\top \mathbf a}$ be the projection matrix . We rewrite eq. (1) as $\mathbf p=P\mathbf b$ . $P$ is a very interesting matrix. What’s the column space of it? Since $\mathbf b$ is an arbitrary vector put to the right of $P$ , and we get $\mathbf p$ from it, no doubt:

$C(P)=the\ line\ thru\ \mathbf a;\\ rank(P)=1$

What else? Hope you notice $P$ is symmetric by looking at the numerator (lecture 5). One other thing is that when we project a vector into $\mathbf a$ twice, it’s the same vector (checkout multiply $\mathbf p$ by $P$ again). Therefore

$P^\top=P;P^2=P$

Why project?

We’ve talked last time that $A\mathbf x=\mathbf b$ may not have solutions. $A\mathbf x$ is in the column space but $\mathbf b$ may not. What can we do is to solve the closest equation to $A\mathbf x=\mathbf b$ , which is

$A\mathbf{\hat x}=\mathbf p\tag{3}$

where $\mathbf p$ is the projection of $\mathbf b$ into the column space of $A$ (you will see why). And we can name this $\mathbf x$ as $\hat{\mathbf x}$ since it’s not the original $\mathbf x$ . So how to do this projection? Similar to above, but this time we want a general formula when $\mathbf a$ is no longer a line. So imagine $C(A)$ is a plane, constituted by the linear combinations of column vectors in $A$ which are $\mathbf a_1,\mathbf a_2,…\mathbf a_n$ .

$A=\begin{bmatrix} \vert & \vert &...&\vert&\vert\\ \mathbf a_1&\mathbf a_2 & ... & \mathbf a_{n-1} & \mathbf a_n\\ \vert & \vert &...&\vert&\vert\\ \end{bmatrix}$

Since there’re many vectors in $C(A)$ , we need to pick the $\mathbf p$ so that it can give us the closest approximations to $\mathbf b$ . This happens when we have a perpendicular projection from $\mathbf b$ to $\mathbf p$ . That is, $\mathbf e=\mathbf b-\mathbf p$ , and $\mathbf e$ is perpendicular to $C(A)$ . Being perpendicular to a whole matrix means it is perpendicular to every column in it. First $\mathbf a_1^\top \mathbf e=0$ . The vectors on the plane of $C(A)$ is perpendicular to $\mathbf e$ , so are other vectors $\mathbf a_2^\top \mathbf e=0,…,\mathbf a_n^\top \mathbf e=0$ . Therefore,

$\begin{align} \mathbf a_1^\top \mathbf e+\mathbf a_2^\top \mathbf e+…+\mathbf a_n^\top \mathbf e&=0\\ \begin{bmatrix} \mathbf a_1^\top&...&\mathbf a_n^\top \end{bmatrix}&\mathbf e=0\\ A^\top \mathbf e&=0\\ \end{align}$

From this we can solve for $\mathbf {\hat x}$ in terms of original $\mathbf b$ :

$\begin{align} A^\top \mathbf e&=0\\ A^\top (\mathbf b-A\hat{\mathbf x})&=0\\ \end{align}\tag{4}$

Solve eq. (4):

$\begin{align} A^\top (\mathbf b-A\hat{\mathbf x})&=0\\ A^\top \mathbf b&=A^\top A\hat{\mathbf x}\\ A^\top A\hat{\mathbf x}&=A^\top \mathbf b\\ \hat{\mathbf x}&=(A^\top A)^{-1}A^\top \mathbf b \end{align}\tag{5}$

Then the projected vector $\mathbf p$ is just

$\mathbf p=A(A^\top A)^{-1}A^\top \mathbf b$

And the projection matrix $P$ is

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

Warning: since $A$ is not required to be a square matrix, we cannot do $(A^\top A)^{-1}=A^{-1}A^{\top -1}$ . $A^\top A$ is square. But still, $A^\top A$ is invertible if only if $A$ is full column rank.