Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hi: Suppose I have a matrix $Y$ is that is $p\times q$ and of rank $r$. Then I read a paper that said that the SVD can be decomposed as $Y=U_0 \Sigma_0 V^*_0 + U_1 \Sigma_1 V*_1$ where $U_0$ and $V_0$ are the singular vectors associated with the singular values greater than $\tau$ and $U_1$ and $V_1$ are the singular vectors associated with singular values less than $\tau$. Also $*$ denotes the transpose of a matrix.

Could someone tell me what the dimensions of the various submatrices are so that the decomposition is true. You can assume whatever you want about the number of eigenvalues greater than $\tau$ and the number of eigenvalues less than $\tau$. I'm trying to understand how the original $Y$ can be written that way. I understand that it can be written as $Y = U \Sigma V^*$ which is the regular SVD but I don't understand how this regular SVD can be broken down into the form at the top with the sub-matrices. Thanks. Also, if there's a paper or book that shows it, that's fine also.

share|improve this question
add comment

2 Answers

Any matrix $A \in \mathbb{C}^{m \times n}$ has a singular value decomposition given by $$A = U_{m \times r} \Sigma_{r \times r} V_{r \times n}^*$$ where $r$ is the rank of the matrix $A$. The matrices $U_{m \times r}$ and $V_{n \times r}$ are orthonormal matrices i.e. $U^*U = I_{r \times r}$ and $V^* V = I_{r \times r}$. The matrix $\Sigma_{r \times r}$ is a diagonal matrix with its diagonal entries $$\Sigma_{11} \geq \Sigma_{22} \geq \Sigma_{33} \geq \cdots \geq \Sigma_{rr} > 0$$ i.e. $$A = \underbrace{\begin{bmatrix} \vec{u}_1 & \vec{u}_2 & \cdots & \vec{u}_r\end{bmatrix}}_{U} \underbrace{\begin{bmatrix} \Sigma_{11} & 0 & 0 & \cdots & 0\\0 & \Sigma_{22} & 0 & \cdots & 0\\ 0 & 0 & \Sigma_{33} & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \Sigma_{rr}\end{bmatrix}}_{\Sigma} \underbrace{\begin{bmatrix} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_r\end{bmatrix}^*}_{V^*}$$ where $\vec{u}_k \in \mathbb{C}^{m \times 1}, \vec{v}_k \in \mathbb{C}^{n \times 1}$ and $\vec{u}_j \cdot \vec{u}_{k} = \vec{v}_j \cdot \vec{v}_{k} = \delta_{jk}$.

Note that the above decomposition can also be written as shown below. $$A = \Sigma_{11} \vec{u}_1 \vec{v}_1^* + \Sigma_{22} \vec{u}_2 \vec{v}_2^* + \Sigma_{33} \vec{u}_3 \vec{v}_3^* + \cdots + \Sigma_{rr} \vec{u}_r \vec{v}_r^*$$

If we have that $$\Sigma_{11} \geq \Sigma_{22} \geq \Sigma_{33} \geq \cdots \geq \Sigma_{\ell \ell} > \tau \geq \Sigma_{\ell+1,\ell+1} \geq \cdots \geq \Sigma_{rr} > 0$$ then we can write $A$ as $$A = \underbrace{\Sigma_{11} \vec{u}_1 \vec{v}_1^* + \Sigma_{22} \vec{u}_2 \vec{v}_2^* + \cdots + \Sigma_{\ell, \ell} \vec{u}_{\ell} \vec{v}_{\ell}^*}_{A_{\ell}} + \underbrace{\Sigma_{\ell+1, \ell+1} \vec{u}_{\ell+1} \vec{v}_{\ell+1}^* + \cdots + \Sigma_{rr} \vec{u}_r \vec{v}_r^*}_{A-A_{\ell} = \tilde{A}_{\ell}}$$ Now note that $A_r$ can be written as $$A_{\ell} = \underbrace{\begin{bmatrix} \vec{u}_1 & \vec{u}_2 & \cdots & \vec{u}_{\ell}\end{bmatrix}}_{U^{(\ell)}} \underbrace{\begin{bmatrix} \Sigma_{11} & 0 & 0 & \cdots & 0\\0 & \Sigma_{22} & 0 & \cdots & 0\\ 0 & 0 & \Sigma_{33} & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \Sigma_{{\ell},{\ell}}\end{bmatrix}}_{\Sigma^{(\ell)}} \underbrace{\begin{bmatrix} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_{\ell}\end{bmatrix}^*}_{V^{(\ell)^*}}$$ and $$\tilde{A}_{\ell} = \underbrace{\begin{bmatrix} \vec{u}_{\ell+1} & \vec{u}_{\ell+2} & \cdots & \vec{u}_{r}\end{bmatrix}}_{\tilde{U}^{(\ell)}} \underbrace{\begin{bmatrix} \Sigma_{{\ell+1},{\ell+1}} & 0 & \cdots & 0\\0 & \Sigma_{{\ell+2},{\ell+2}} & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \Sigma_{r,r}\end{bmatrix}}_{\tilde{\Sigma}^{(\ell)}} \underbrace{\begin{bmatrix} \vec{v}_{\ell+1} & \vec{v}_{\ell+2} & \cdots & \vec{v}_{r}\end{bmatrix}^*}_{\tilde{V}^{(\ell)^*}}$$ where $\vec{u}_k \in \mathbb{C}^{m \times 1}, \vec{v}_k \in \mathbb{C}^{n \times 1}$ and $\vec{u}_j \cdot \vec{u}_{k} = \vec{v}_j \cdot \vec{v}_{k} = \delta_{jk}$.

Hence, you have the decomposition $$A = \underbrace{U^{(\ell)} \Sigma^{(\ell)} V^{(\ell)^*}}_{A_{\ell}} + \underbrace{\tilde{U}^{(\ell)} \tilde{\Sigma}^{(\ell)} \tilde{V}^{(\ell)^*}}_{\tilde{A}_{\ell}}$$ where the singular values of $\tilde{A}_{\ell}$ are not greater than $\tau$.

share|improve this answer
add comment

To supplement Marvis's answer with an illustrative example, consider $\tau=4.5$ and \begin{align} Y &= \frac12\begin{bmatrix} 5& 4& \epsilon\\ 5&-4& \epsilon\\ 5& 4&-\epsilon\\ 5&-4&-\epsilon \end{bmatrix}\\ &= \underbrace{\begin{bmatrix} 0.5& 0.5& 0.5& 0.5\\ 0.5&-0.5& 0.5&-0.5\\ 0.5& 0.5&-0.5&-0.5\\ 0.5&-0.5&-0.5& 0.5 \end{bmatrix}}_{U} \underbrace{\begin{bmatrix} 5&0&0\\ 0&4&0\\ 0&0&\epsilon\\ 0&0&0 \end{bmatrix}}_{\Sigma} \underbrace{\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}}_{V^\ast}\\ &= \underbrace{\begin{bmatrix} 0.5\\ 0.5\\ 0.5\\ 0.5 \end{bmatrix}}_{U_0} \underbrace{\begin{bmatrix} 5 \end{bmatrix}}_{\Sigma_0} \underbrace{\begin{bmatrix} 1&0&0 \end{bmatrix}}_{V_0^\ast} + \underbrace{\begin{bmatrix} 0.5& 0.5\\ -0.5& 0.5\\ 0.5&-0.5\\ -0.5&-0.5 \end{bmatrix}}_{U_1} \underbrace{\begin{bmatrix} 4&0\\ 0&\epsilon \end{bmatrix}}_{\Sigma_1} \underbrace{\begin{bmatrix} 0&1&0\\ 0&0&1 \end{bmatrix}}_{V_1^\ast}. \end{align} In general, suppose $Y$ is $p\times q$ and $k$ of its singular values are greater than $\tau$. If $s=\min(m,n)-k$, then the dimensions of the matrices in the decomposition are given by: \begin{align} \underbrace{Y}_{p\times q} &= \underbrace{U}_{p\times p}\underbrace{\Sigma}_{p\times q}\underbrace{V^\ast}_{q\times q}\\ &= \underbrace{U_0}_{p\times k}\underbrace{\Sigma_0}_{k\times k}\underbrace{V_0^\ast}_{k\times q} + \underbrace{U_1}_{p\times s}\underbrace{\Sigma_1}_{s\times s}\underbrace{V_1^\ast}_{k\times q}. \end{align} Some literature adopts (so does Marvis's answer) the convention of a "thin/economic SVD", in which only the nonzero diagonal entries of $\Sigma$ in a regular SVD are regarded as singular values, and the zero columns of $\Sigma$ in the regular SVD are omitted. In this case, if $\mathrm{rank}(Y)=r$ and $t=r-k$, then the dimensions of the matrices become: \begin{align} \underbrace{Y}_{p\times q} &= \underbrace{U}_{p\times r}\underbrace{\Sigma}_{r\times r}\underbrace{V^\ast}_{r\times q}\\ &= \underbrace{U_0}_{p\times k}\underbrace{\Sigma_0}_{k\times k}\underbrace{V_0^\ast}_{k\times q} + \underbrace{U_1}_{p\times t}\underbrace{\Sigma_1}_{t\times t}\underbrace{V_1^\ast}_{t\times q}. \end{align} For instance, if $\epsilon=0$ in our example, the decomposition would become \begin{align} Y &= \frac12\begin{bmatrix} 5& 4&0\\ 5&-4&0\\ 5& 4&0\\ 5&-4&0 \end{bmatrix}\\ &= \underbrace{\begin{bmatrix} 0.5& 0.5\\ 0.5&-0.5\\ 0.5& 0.5\\ 0.5&-0.5 \end{bmatrix}}_{U} \underbrace{\begin{bmatrix} 5&0\\ 0&4 \end{bmatrix}}_{\Sigma} \underbrace{\begin{bmatrix} 1&0&0\\ 0&1&0 \end{bmatrix}}_{V^\ast}\\ &= \underbrace{\begin{bmatrix} 0.5\\ 0.5\\ 0.5\\ 0.5 \end{bmatrix}}_{U_0} \underbrace{\begin{bmatrix} 5 \end{bmatrix}}_{\Sigma_0} \underbrace{\begin{bmatrix} 1&0&0 \end{bmatrix}}_{V_0^\ast} + \underbrace{\begin{bmatrix} 0.5\\ -0.5\\ 0.5\\ -0.5 \end{bmatrix}}_{U_1} \underbrace{\begin{bmatrix} 4 \end{bmatrix}}_{\Sigma_1} \underbrace{\begin{bmatrix} 0&1&0 \end{bmatrix}}_{V_1^\ast}. \end{align} Hope this helps.

share|improve this answer
    
both of these answers look amazing but my brain needs to be on all cylinders so I'll go over them tomorrow. I really appreciate the details and efforts that went into both of your answers. I'm new to this site and my first impressions from your answers is that it's a pretty amazing place. –  mark leeds Nov 18 '12 at 7:47
    
thank you marvin and user1551. both of your answers were amazingly clear and thorough. I really appreciate it and I'm so glad that I found this list. –  mark leeds Nov 19 '12 at 0:24
    
You are welcome :-) –  user1551 Nov 19 '12 at 12:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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