1
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Daniel Sep 27 '14 at 13:17
  • $\begingroup$ 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. $\endgroup$ – steve Sep 27 '14 at 19:54
  • $\begingroup$ 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. $\endgroup$ – Daniel Sep 27 '14 at 20:14
1
$\begingroup$

Filling in the details of @Daniel's suggestion.

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*} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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