rank-d Projection Matrix

Question

I am trying to prove the following:

Given $1 \le d \le n$, a matrix $P \in R^n$ is a rank-$d$ orthogonal projection matrix. Prove that P is projection matrix iff there exists a $n$x$d$ matrix $U$ such that $P =UU^T$ and $U^TU = I$.

I know that this is an obvious fact about projection matrices but I am not sure how to get started on proving it.

Once I can do that, I am looking to prove that,

for all $v \in R^n$, $Pv = arg \min_{w \in range(P)} \lVert {v - w} \rVert^2$

Answer 1

We can prove the equivalence by proving both ways separately.

---

1. $ P =UU^T,U^T U = I \Rightarrow $ P is a projection matrix

Let's solve an objective similar to the one you stated: $$ \arg \min_{b \in R^n} \lVert {v - Pb} \rVert^2$$ In other words, given any vector $v$, what is the corresponding vector $b$ such that some vector in the column space of $P$ is 'closest' to $v$ (closest in the 2-norm sense).

Next, since $$ Pb = U U^T b$$ the objective is $$ \arg \min_{b \in R^n} \lVert {v - U U^T b} \rVert^2 $$ which can be rewritten, using $U^T U = I$ as: $$ \arg \min_{b \in R^n} (v - U U^T b)^T (v - U U^T b) = \arg \min_{b \in R^n} v^Tv - 2 v^T U U^T b + b^T U U^T b $$ The minimum is found by setting the derivative with respect to the vector $b$ equal to zero. $$ 0 = - 2 U U^T v + 2 U U^T b $$ which means $\forall v$, the optimal $b$ is $v$: $$ U U^T v = U U^T b \Rightarrow P v = P b$$ So we know the original problem is, for every $v$: $$ \arg \min_{b \in R^n} \lVert {v - Pb} \rVert^2 = \lVert {v - Pv} \rVert^2$$ Since for every $v$, $P v$ is the vector in the column space of $P$ that is 'closest' to $v$ , $P$ must be a projection matrix.

---

2. $P$ is a projection matrix $ \Rightarrow P =UU^T,U^T U = I $

Since $P$ is a projection matrix, $Pb$ is the projection of vector $b$ onto some rank-d columnspace represented by the columns of matrix $X \in R^{n\times d}$. Since $X$ is a rank-d matrix it has $d$ linearly independent columns. Make the columns of $X$ orthonormal using Gram Schmidt.

We can use the well-known formula for projections: $$ P = X (X^T X)^{-1} X^T $$ Since the columns of $X$ are orthonormal, $(X^T X)^{-1} =I$, so: $$ P = X X^T $$ Let $U=X$ and we have $$ P = U U^T, (U^T U)^{-1} =I = U^T U $$

Answer 2

($\Rightarrow$) Let $P=UU^T$ and $U^TU=I$. Then $P^2=UU^TUU^T=UU^T=P$ and $P^T=P$.

($\Leftarrow$) Let $P^2=P$ and $P^T=P$. Since $P$ is an orthogonal projection it has eigenvalues $0$ or $1$ and it is unitarily diagonalizable. So there exist an orthogonal $V$ such that $$P=\begin{bmatrix}V_1 & V_2\end{bmatrix}\begin{bmatrix}I_d & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}V_1^T \\ V_2^T\end{bmatrix} = V_1V_1^T$$ Also $V^TV=I$ which implies $$\begin{bmatrix}V_1^T \\ V_2^T\end{bmatrix}\begin{bmatrix}V_1 & V_2\end{bmatrix}=\begin{bmatrix}V_1^TV_1 & V_1^TV_2 \\ V_2^TV_1 & V_2^TV_2\end{bmatrix}=\begin{bmatrix}I_d & 0 \\ 0 & I_{n-d}\end{bmatrix}$$