# Orthonormal Projection Proof

Let $u_1,\ldots,u_k$ be an orthonormal basis for the subspace $W \subset \mathbb{R}^m$. Let $A = (u_1u_2\ldots u_k)$ be the $m \times k$ matrix whose columns are the orthonormal basis vectors, and define $P=AA^T$ to be the corresponding projection matrix.

a.) Given $v \in \mathbb{R}^n$, prove that its orthogonal projection $w \in W$ is given by matrix multiplication $w=Pv$

I am trying to understand what exactly is going on in this question. Here is an illustration I found that I wish you guys can help me understand. Correct me if I am wrong in any of my analysis of this image.

On this image the subspace $W\subset \mathbb{R}^m$ is the plane. The orthogonal basis $u_1,\ldots,u_k$ is the vectors $u_1, u_2$. Given $v\in \mathbb{R}^n$ I am not sure what represents that in the image, will it be $h^*_N$? For $w\in W$, will it be the orthogonal vector $f$ in the image?

My attempt:

I notice that $P =AA^T$ is equivalent to the least square solution. Also, will $v\in \mathbb{R}^n$ be orthogonal to every vector in the subspace $W$, so then $v = w - u$, where $u = c_1u_1,\ldots,c_ku_k$?

I will have to prove that w (which will equal the vector $f$ in the image) was given by $w=Pv$? Or is $v\in \mathbb{R}^n$ just $A^T$ since it is in $\mathbb{R}^n$ and not in $\mathbb{R}^m$ (which also I am having trouble understanding what exactly does $\mathbb{R}^n$ and $\mathbb{R}^m$ mean?).

Any thorough explanation will be greatly appreciated!

-
On the picture, the vector $v$ is denoted $f$, the projection $w$ is denoted $w_N^*$, and $h_N^* = v-w$. – Joel Cohen Nov 23 '12 at 1:39
@JoelCohen thanks for pointing that out. That helps a lot! – diimension Nov 23 '12 at 1:43

Note that $$\vec{w} = \sum_{r=1}^{k} \alpha_r \vec{u}_r = A\begin{bmatrix} \alpha_1, \alpha_2, \ldots, \alpha_k\end{bmatrix}^T = A \vec{\alpha}$$ Since $w$ is the orthogonal projection of $\vec{v}$, we have that $(\vec{v} - \vec{w}) \cdot \vec{u}_r = 0$ for all $\vec{u}_r$. Hence, we get that $$(v - w)^T u_r = 0\implies (v-w)^T A = 0 \implies A^T(v-w) = 0 \implies A^T v = A^T w = A^T A \alpha$$ Since the columns of $A$ are orthonormal, we have that $A^T A = I$. Hence, we get that $\alpha = A^Tv$. Hence, $$w=A \alpha = A A^T v$$

-
Thank you very much for explaining that, Marvis! – diimension Nov 23 '12 at 3:34
Marvis, sry to bother you on this question again but I have a question regarding the image above. Lets say I have two basis $u_1$ and $u_2$ in the subspace $W$, which is denoted as the plane on the image. Can those two basis be orthogonal? – diimension Nov 28 '12 at 7:58
@diimension Yes, for any subspace $W$ you can find an orthonormal basis. Also, only under the above assumption, we get $w = AA^Tv$ else there will be $(A^TA)^{-1}$ term hanging around. Since $u$'s are orthonormal, we get that $(A^TA) = I$. – user17762 Nov 28 '12 at 8:01
I understand now, thanks again! – diimension Nov 28 '12 at 8:08

Write $v$ as $$v = w + w^{\perp},$$ so $w^{\perp}$ is orthogonal to $W$. Note that $w$ is in the column space of $A$, so $\exists \, c$ such that $w = Ac$. Hence $$v = Ac + w^{\perp}.$$ Now multiply both sides by $A^T$ to obtain \begin{align*} A^T v &= A^T A c + A^T w^{\perp}\\ &= c. \end{align*} It follows that $w = A A^T v$.

-
Thank you very much for explaining that, LittleO! – diimension Nov 23 '12 at 3:34

The natural way to project onto $W$ is by projecting into each of its "coordinates", which in this case are the $u_1,\ldots,u_k$. So $$Pw=\sum_{j=1}^k(u_j^Tw)\,u_j=\sum_{j=1}^k\,u_j(u_j^Tw)=\left(\sum_{j=1}^k\,u_ju_j^T\right)w=AA^Tw$$

-
Thanks for that info! – diimension Nov 23 '12 at 5:43

In terms of multi-linear algebra, think of the matrix $A$ as a direct sum of the $u_i$ and of its transpose as a direct sum of $\varphi_i$ (its duals), then that matrix multiplication is just a direct sum of the terms of the form $u_i \otimes \varphi_i$, each of which is a projection onto the subspace span($u_i$).

-