What are the dimensions of the singular vectors matrices in the singular value decomposition?

Question

Consider a $p\times q$ matrix $Y$ with rank $r$.

I read in a paper that the SVD can be written 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.

Answer 1

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

Answer 2

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.