Low rank approximation using the SVD

I have been looking at some LSI implementation which assumes that the following property always hold:

Given the Singular Value Decomposition of a real matrix $A$, $$A = U\Sigma V^T$$ and its approximation at the first $k$ singular values: $$\hat{A_k} = U_k \Sigma_k V_k^T$$ it holds: $$\hat{A_k} = U_k \Sigma_k V_k^T=AV_kV_k^T$$

Can you help me proving that this is true (or false) ?

Edit: I have found this proof.

The $V$ matrix is orthonormal, so $V^{-1} = V^T$, therefore: $$AV = U\Sigma$$ and then truncating at the same level: $$AV_k = U_k \Sigma_k$$

However, I'm not very convinced by this last step, do you think that it is correct?

• Unless I'm doing something silly its not true in general. Suppose $V$ is real. By definition, $V$ is unitary (thus, $VV^T=I$), hence so is $V_k$. So $V_kV_k^T=I$, so $\hat{A}_k=AV_kV_k^T=AI=A$. This can only be true if $A$ has rank $k$. – jkn May 13 '13 at 10:56
• Hi, I think that what you say is not correct; infact $VV^T = I$ by definition, but $V_k V_k^T$ isn't! – Aslan986 May 13 '13 at 12:26
• Sorry, I misread, you are right. The last step is fine (see below - it wouldn't fit into a comment). – jkn May 13 '13 at 15:21

The last step is fine, just break $AV=U\Sigma$ into blocks and carry out the matrix multiplication. In particular, suppose $A$ is $n\times m$ and of rank $r$ and that $k\leq r$. Then,

$$\underbrace{U}_{n\times r}=\begin{bmatrix}U_k|\tilde{U}\end{bmatrix},\quad \underbrace{\Sigma}_{r\times r}=\begin{bmatrix}\Sigma_k&|&0\\\hline0&|&\tilde{\Sigma}\end{bmatrix},\quad \underbrace{V^T}_{r\times m}=\begin{bmatrix}V_k^T\\\hline \tilde{V}^T\end{bmatrix}$$

where $U_k$ is $n\times k$, $\tilde{U}$ is $n\times r-k$, $\Sigma_k$ is $k\times k$, $\tilde{\Sigma}$ is $r-k\times r-k$, $V_k$ is $m\times k$ and $\tilde{V}$ is $m\times r-k$. So,

$$AV=A\begin{bmatrix} V_k |\tilde{V}\end{bmatrix}=\begin{bmatrix} AV_k |A\tilde{V}\end{bmatrix},$$

$$U\Sigma=\begin{bmatrix}U_k|\hat{U}\end{bmatrix}\begin{bmatrix}\Sigma_k&|&0\\\hline0&|&\tilde{\Sigma}\end{bmatrix}=\begin{bmatrix}U_k\Sigma_k|\tilde{U}\tilde{\Sigma}\end{bmatrix}.$$

Thus,

$$AV=U\Sigma\Leftrightarrow \begin{bmatrix} AV_k |A\tilde{V}\end{bmatrix}=\begin{bmatrix}U_k\Sigma_k|\hat{U}\tilde{\Sigma}\end{bmatrix}\Rightarrow AV_k=U_k\Sigma_k.$$