Economic form of the singular value decomposition

Question

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

Answer 1

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!