# Economic form of the singular value decomposition

Let

• $$m,n\in\mathbb N$$
• $$A\in\mathbb R^{m\times n}$$ and $$|A|:=\sqrt{A^TA}$$
• $$r:=\operatorname{rank}A$$
• $$\sigma_1,\ldots,\sigma_r$$ denote the singular values of $$A$$ and $$\sigma_i:=0$$ for $$i\in\{r+1,\ldots,n\}$$,
• $$\Sigma:=\operatorname{diag}(\sigma_1,\ldots,\sigma_n)$$

By the polar decomposition theorem, $$A=W|A|\tag1$$ for some partial isometry $$W\in\mathbb R^{m\times n}$$ with $$\mathcal N(W)=\mathcal N(A)\tag2.$$ By the spectral theorem, $$|A|=\sum_{i=1}^r\sigma_ie_i\otimes e_i\tag3$$ for some orthonormal basis $$(e_1,\ldots,e_r)$$ of $$\mathcal R(|A|)$$. Let $$(\tilde e_1,\ldots,\tilde e_n)$$ denote the standard basis of $$\mathbb R^n$$. By definition, $$\Sigma=\sum_{i=1}^n\sigma_i\tilde e_i\otimes\tilde e_i\tag4.$$ Supplement $$(e_1,\ldots,e_r)$$ to an orthonormal basis $$(e_1,\ldots,e_n)$$ of $$\mathbb R^n$$. Then $$V:=\sum_{i=1}^n\tilde e_i\otimes e_i\in\mathbb R^{n\times n}$$ is orthogonal, $$U:=WV=\sum_{i=1}^n\tilde e_i\otimes\underbrace{We_i}_{=:\:f_i}\in\mathbb R^{m\times n}\tag5$$ is a partial isometry, $$(f_1,\ldots,f_r)$$ is an orthonormal basis of $$\mathcal R(A)$$ and $$A=U\Sigma V^T\tag6.$$

How precisely do we need to alter $$U$$ and $$\Sigma$$ so that they belong to $$\mathbb R^{m\times m}$$ and $$\mathbb R^{m\times n}$$, respectively, $$U$$ is orthogonal and $$(6)$$ remains to hold?

Note that $$r\le\min(m,n)$$. I'm not sure what we need to do with $$(f_{r+1},\ldots,f_n)$$, but they are not necessarily orthogonal, since $$W$$ is only an isometry on $$\mathcal N(W)^\perp$$. I guess we need to treat the cases $$m\le n$$ and $$m\ge n$$ separately.

EDIT: Note that $$\Sigma=\sum_{j=1}^r\sigma_i\tilde e_i\otimes\tilde e_i\tag7$$ and $$U\Sigma=\sum_{k=1}^r\sigma_k\tilde e_k\otimes f_k\tag8.$$ Now, if $$m\le n$$, then $$\sigma_{m+1}=\cdots=\sigma_n=0\tag9$$ and hence $$\tilde U\tilde\Sigma=U\Sigma\tag{10},$$ where $$\tilde U:=\sum_{j=1}^m\tilde e_j\otimes f_j\in\mathbb R^{m\times m}$$ and $$\tilde\Sigma:=\sum_{k=1}^m\sigma_j\tilde e_j\otimes\tilde e_j\in\mathbb R^{m\times n}.$$ But, if I'm not missing anything, $$\tilde U$$ is not orthogonal, since this is equivalent to $$(f_1,\ldots,f_m)$$ being an orthonormal system, but all we know is that $$(f_1,\ldots,f_r)$$ is an orthonormal system. So, I guess we need to replace $$(f_{r+1},\ldots,f_m)$$. By $$(8)$$, this should be possible without violating $$(10)$$.

You are interested in the Reduced Singular Value Decomposition (RSVD). Let us suppose your original SVD had $$U = \begin{bmatrix} \vec{u}_1 & \cdots & \vec{u}_n\end{bmatrix}, ~ \Sigma = \text{diag}(d_1, d_2, \cdots, d_n), ~ V = \begin{bmatrix} \vec{v}_1 & \cdots & \vec{v}_n\end{bmatrix}$$ Let us further assume that the singular values $$d_i$$ are organized from largest to smallest. To take your original SVD and produce the RSVD, we consider the following two cases you mentioned:

1. If $$n < m$$, we can expand the column vectors of $$U$$ to a set of $$m$$ mutually orthogonal vectors (this is always possible since $$n < m$$ and the columns of $$U$$ are in $$\mathbb{R}^m$$), and fill $$D'$$ with zeroes until it is an $$m \times n$$ matrix. That is, $$A = U' D' V^T, ~ \begin{bmatrix} \vec{u}_1 & \cdots & \vec{u}_n & \cdots & \vec{u}_m\end{bmatrix}, ~ D' = \begin{bmatrix} D \\ 0_{(m - n) \times n}\end{bmatrix} = \text{diag}(d_1, \cdots, d_n)$$

2. If $$m \leq n$$, then it follows that the last $$n - r \geq n - m$$ singular values are necessarily zero, since $$A^T A$$ has rank $$r \leq \min(m, n) = m$$. Then the contribution to the SVD from the last $$n - r$$ vectors of $$U$$ will be nothing, and hence we can remove them to obtain the $$m \times r$$ matrix $$U_r$$ which is partially orthogonal. Hence, $$A = U_r D_r V^T, ~ U_r = \begin{bmatrix} \vec{u}_1 & \cdots & \vec{u}_r\end{bmatrix}, ~ D_r = \text{diag}(d_1, d_2, \cdots, d_r)$$ Note that $$D_r$$ is now an $$r \times n$$ diagonal matrix, and also note that $$D_r$$ contains no zero entries along its diagonal. From here, we only need to apply the procedure from the first case. That is, we will complete the basis $$\{\vec{u}_1, \cdots, \vec{u}_r\}$$ to a orthonormal basis for $$\mathbb{R}^m$$ (which is always possible as $$r \leq m$$ and $$\vec{u}_i \in \mathbb{R}^m$$) and set this ordered basis to be the columns of $$U'$$. Then, we fill $$D_r$$ with zeroes until it is $$m \times n$$ to obtain $$D'$$. $$V$$ is left unchanged, and it is now the case that $$A = U' D' V^T$$.

Hope this helps!

• Thank you for your answer. It definitely helps. But I think your $U'$ is still not orthogonal. Please take note of my edit. May 18, 2020 at 19:15
• @0xbadf00d I saw your edit and I have edited my answer. I believe it should be correct now. May 18, 2020 at 19:33
• Thank you for your edit. I think we actually talked about three different forms of the singular value decomposition: The one given in the question, the reduced (or "compact") decomposition (I guess this is the one you initially thought I'm searching for) and the one with an orthogonal $U$ (don't know how it's called). May 21, 2020 at 17:59
• I think we can obtain the reduced decomposition by setting \begin{align}\tilde U&:=\sum_{i=1}^r\tilde e_i\otimes f_i\in\mathbb R^{m\times r},\\\tilde\Sigma&:=\sum_{i=1}^r\sigma_i\tilde e_i\otimes\tilde e_i\in\mathbb R^{r\times r},\\\tilde V&:=\sum_{i=1}^r\tilde e_i\otimes Ve_i\in\mathbb R^{n\times r},\end{align} where $(\tilde e_1,\ldots,\tilde e_r)$ denotes the standard basis of $\mathbb R^r$. Do you agree? With this we should have $\tilde U\tilde\Sigma\tilde V^T=A$. May 21, 2020 at 18:02
• Regarding your current answer: I didn't checked everything, but please note that something seems to be wrong in the second case ($m\le n$). First of all, in $D_r = \text{diag}(d_1, d_2, \cdots, d_m)$, it should be $r$ instead of $m$. Moreover, this is not a $r\times n$-matrix, but a $r\times r$-matrix. Oh, and in the first case you write that we need to do the "reverse of the previous case", but there is no previous case. May 21, 2020 at 18:05