# orthogonal projection onto linear space of matrices

Let $M$ be an $n_1 \times n_2$ matrix with rank $r$ and let $M = U\Sigma V^T$ be its SVD. Define the space $T = \mathrm{span}\{\{ u_k y^T : y \in \mathbb{R}^{n_2}, 1 \leq k \leq r\} \cup \{ x v_k^T : x \in \mathbb{R}^{n_1}, 1 \leq k \leq r\}\}$ where $u_k$ (resp. $v_k$) are the columns of $U$ (resp. $V$). So $T$ is a subspace of $\mathbb{R}^{n_1 \times n_2}$.

How do we show that the orthogonal projection $P_T$ onto $T$ is $$P_T(Z) = P_U Z + Z P_V - P_U Z P_V$$ as claimed in http://pages.cs.wisc.edu/~brecht/papers/09.Recht.ImprovedMC.pdf, Eq. (2.1)?

• First, show that $P_T^2=P_T$. Then show that $P_T$ is self-adjoint with respect to the inner product $\langle A,B\rangle=trace(AB^t)$ $($Here use $P_U^t=P_U,\ P_V^t=P_V)$. Thus, $P_T$ is an orthogonal projection. Finally show that $\Im(P_T)=T($ Here show that $P_T(A)=A$ for every $A\in T$ and notice that $\Im(P_T)\subset T)$. – Daniel Sep 27 '14 at 13:17
• Thanks @Daniel. This verifies the claim for sure. I'm also wondering what the constructive way would be to establish the claim? E.g. if I just told you $T$ and asked what the projection was. – steve Sep 27 '14 at 19:54
• Hi Steve. If you want to obtain the projection onto $span(V\cup W)$, one idea is to obtain the projection on $span(V)$ then add with the projection onto $span(W)$. But see that we are adding twice the projection onto $span(V\cap W)$, thus we must subtract the projection onto $span(V\cap W)$. I believe that is the idea behind this formula. – Daniel Sep 27 '14 at 20:14

First, $P_T$ is a projective operator. To see this, algebra shows that $(P_T^2)(Z) = P_T(P_T(Z))$ is $$P_U Z + P_U Z P_V - P_U Z P_V + P_UZ P_V + Z P_V - P_U Z P_V - (P_UZP_V + P_U Z P_V - P_U Z P_V)$$ where we used $P_U^2 = P_U$ and $P_V^2 = P_V$. This simplifies to $P_U Z + Z P_V - P_U Z P_V = P_T(Z)$.
Second, $P_T$ is self-adjoint w.r.t. the matrix inner product. Let $Z, W$ be arbitrary matrices. Then \begin{align*} \langle P_T(Z), W \rangle &= \mathrm{Tr}((P_T(Z))^T W) \\ &= \mathrm{Tr}( Z^T P_U W + P_V Z^T W - P_V Z^T P_U W) \\ &\stackrel{(a)}{=} \mathrm{Tr}( Z^T P_U W + Z^T W P_V - Z^T P_U W P_V) \\ &= \mathrm{Tr}( Z^T( P_U W + W P_V + P_U W P_V ) ) \\ &= \langle Z, P_T(W) \rangle \end{align*} where in (a) we used the cyclic and linear properties of trace
Now we have established $P_T$ is an orthogonal projection since a projection is orthogonal iff it is self-adjoint. What's left to show is that $P_T(Z) = Z$ for any $Z \in T$. Let $Z \in T$. Then we can write $Z$ as $$Z = \sum_{i=1}^{r} \alpha_i u_i y^T + \sum_{i=1}^{r} \beta_i x v_i^T := \widetilde{U} + \widetilde{V}$$ for $\alpha_i,\beta_i \in \mathbb{R}$ and vectors $x,y$. It is not hard to show that $P_U \widetilde{U} = U$ and $\widetilde{V} P_V = \widetilde{V}$. Then \begin{align*} P_T(\widetilde{U} + \widetilde{V}) &= P_U \widetilde{U} + P_U \widetilde{V} + \widetilde{U} P_V + \widetilde{V} P_V - P_U \widetilde{U} P_V - P_U \widetilde{V} P_V \\ &= \widetilde{U} + P_U \widetilde{V} + \widetilde{U} P_V + \widetilde{V} - \widetilde{U} P_V - P_U \widetilde{V} \\ &= \widetilde{U} + \widetilde{V} \end{align*}