# decomposition of singular value decomposition

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.

-

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

-

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.

-
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