Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 2

up vote 3 down vote accepted

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$.

share|improve this answer
1  
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.

share|improve this answer
    
Beautiful, thank you very much Martini! –  diimension Nov 3 '12 at 23:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.