1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – jkn May 13 '13 at 10:56
  • $\begingroup$ Hi, I think that what you say is not correct; infact $VV^T = I$ by definition, but $V_k V_k^T$ isn't! $\endgroup$ – Aslan986 May 13 '13 at 12:26
  • $\begingroup$ Sorry, I misread, you are right. The last step is fine (see below - it wouldn't fit into a comment). $\endgroup$ – jkn May 13 '13 at 15:21
2
$\begingroup$

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

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