Orthogonal Projection Proof

Let $w_1,...,w_n$ be any basis of the subspace $W \subset \mathbb{R^m}$. Let $A = (w_1,...,w_n)$ be the $m$ x $n$ matrix whose columns are the basis vectors, so that $W = rngA$ and $rankA=n$. Let $P = A(A^TA)^{-1}A^T$ be the corresponding projection matrix.

a.) Prove that the orthogonal projection of $v \in \mathbb{R^n}$ onto $w \in W$ is obtained by multiplying by the projection matrix: $w=Pv$.

b.) Show that if $A=QR$, then $P = QQ^T$. Why is $P \ne I$?

How will I be able to prove these?

-
Are there some conditions on $Q$ and $R$? –  copper.hat Nov 3 '12 at 23:30
For the first part consider $\operatorname{rng}(P)$ and $Pw_i$. –  Julian Kuelshammer Nov 3 '12 at 23:30
@copper.hat To me it sounds like en.wikipedia.org/wiki/QR_decomposition –  Julian Kuelshammer Nov 3 '12 at 23:33
Or alternatively, note that $v$ is a solution to the problem $\min_{w \in W} \|w-v\|^2 = \min_x \|Ax-v\|^2$ and look at the first order optimality conditions at the solution... –  copper.hat Nov 3 '12 at 23:33
I see now, he is using the reduced QR decomposition where $R$ is square. I think of the Q in the QR decomposition as being unitary... –  copper.hat Nov 3 '12 at 23:42

2 Answers

For part b), note that $A^T A = R^T Q^T Q R = R^T R$, so \begin{align*} P &= QR(R^T R)^{-1} R^T Q^T \\ &= Q R R^{-1} R^{-T} R^T Q^T \\ &= Q Q^T. \end{align*}

For part a), suppose $b \in \mathbb{R}^m$, and let $\hat{b} = A \hat{x}$ be the projection of $b$ onto $W$. The residual $b - A \hat{x}$ is orthogonal to $W$, hence it is orthogonal to each of the columns of $A$. This tells us that \begin{align*} &A^T (b - A \hat{x}) = 0 \\ \implies & A^T A \hat{x} = A^T b \\ \implies& \hat{x} = (A^T A)^{-1} A^T b \\ \implies& A \hat{x} = A (A^T A)^{-1} A^T b \\ \implies& \hat{b} = A (A^T A)^{-1} A^T b. \end{align*}

This shows that the matrix $P = A (A^T A)^{-1} A^T$ projects onto $W$.

-
Beautiful, thank you very much, LittleO!! –  diimension Nov 3 '12 at 23:53

(a) Let $1 \le i \le n$, we have by noting that $Ae_i = w_i$ ($e_i$ the standard unit vector) \begin{align*} Pw_i &= A(A^TA)^{-1}A^Tw_i\\ &= A(A^TA)^{-1}A^TAe_i\\ &= Ae_i\\ &= w_i \end{align*} so $P$ acts as the identity on $W$. Now let $z \in W^\bot$, then we have $A^Tz = \sum_{i=1}^n w_i^Tz = \sum_i 0 =0$ so $Pz = 0$ and $P$ acts as $0$ on $W^\bot$. That is, $P$ is the orthogonal projection on $W$.

(b) Let $A = QR$ be the QR-decomposition, that is $Q$ is $m \times n$ with orthogonal columns and $R$ is upper triangular. We have \begin{align*} A^TA &= R^TQ^TQR\\ (A^TA)^{-1} &= R^{-1}(Q^TQ)^{-1}R^{-T}\\ A(A^TA)^{-1}A^T &= QRR^{-1}(Q^TQ)^{-1}R^{-T}R^TQ^T\\ &= Q(Q^TQ)^{-1}Q^T \end{align*} As $Q$ has orthogonal columns $Q^TQ = \mathrm{Id}$, and therefore $P = A(A^TA)^{-1}A^T = QQ^T$. $P \ne \mathrm{Id}$ holds exactly iff $n < m$ as then $P$ is a projection onto a proper subspace.

-
Beautiful, thank you very much Martini! –  diimension Nov 3 '12 at 23:53