2
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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!

$\endgroup$
5
  • 1
    $\begingroup$ Thank you for your answer. It definitely helps. But I think your $U'$ is still not orthogonal. Please take note of my edit. $\endgroup$
    – 0xbadf00d
    May 18, 2020 at 19:15
  • 1
    $\begingroup$ @0xbadf00d I saw your edit and I have edited my answer. I believe it should be correct now. $\endgroup$
    – paulinho
    May 18, 2020 at 19:33
  • $\begingroup$ 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). $\endgroup$
    – 0xbadf00d
    May 21, 2020 at 17:59
  • $\begingroup$ 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$. $\endgroup$
    – 0xbadf00d
    May 21, 2020 at 18:02
  • $\begingroup$ 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. $\endgroup$
    – 0xbadf00d
    May 21, 2020 at 18:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .