Are reduced SVD and truncated SVD the same thing?

Question

Truncated SVD: http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html

Reduced SVD, I thought this is essentially the same thing, and it appears to be actually more commonly called this way.

If you could provide reference, that'll be great.

Answer 1

Suppose the shape of $A$ is $m \times n$, written as $\underset{m \times n}{A}$, with rank $r$.

In full SVD:

• $U$ is composed of $r$ orthonormal columns that span the column space of $A$ and $m - r$ orthonormal columns that span the left null space of $A$.
• $\Sigma$ is diagonal and composed of the square root of eigenvalues of $A^T A$ (or $A A^T$) padded with zero rows and columns to be of shape $m \times n$. The diagonal elements are also called the singular values of $A$.
• $V$ is composed of $r$ orthonormal columns that span the row space of $A$ and $n - r$ orthonormal columns that span the null space of $A$.

\begin{align} \underset{m\times n}{A} &= \underset{m \times m,}{U} \underset{m \times n,}{\Sigma} \underset{n \times n}{V^{T}} \end{align}

In reduced SVD:

• the $m-r$ columns that span the left null space are removed from $U$.
• the padded rows and columns of zeros are removed from $\Sigma$.
• the $n-r$ columns that span the null space are removed from $V$.

so it becomes

\begin{align} \underset{m\times n}{A} &= \underset{m \times r,}{U_r} \underset{r \times r,}{\Sigma_r} \underset{r \times n}{V_r^{T}} \end{align}

Note, both reduced SVD and full SVD results in the original $A$ with no information loss.

In truncated SVD, we take $k$ largest singular values ($0 \lt k \lt r$, thus truncated) and their corresponding left and right singular vectors,

\begin{align} \underset{m\times n}{A} &\approx \underset{m \times k,}{U_t} \underset{k \times k,}{\Sigma_t} \underset{k \times n}{V_t^{T}} \end{align}

$A$ constructed via truncated SVD is an approximation to the original A.

Example 1

For $A = \begin{bmatrix} 1 & 1 & 0 \\ 2 & 2 & 0 \\ \end{bmatrix}$, where $m = 2$, $n = 3$, and $r = 1$.

Full SVD:

\begin{align*} \begin{bmatrix} 1 & 1 & 0 \\ 2 & 2 & 0 \\ \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{5}} & \color{Blue}{- \frac{2}{\sqrt{5}}} \\ \frac{2}{\sqrt{5}} & \color{Blue}{\frac{1}{\sqrt{5}}} \end{bmatrix} \begin{bmatrix} \sqrt{10} & \color{Gray}{0} & \color{Gray}{0} \\ \color{Gray}{0} & \color{Gray}{0} & \color{Gray}{0} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \color{Red}{- \frac{1}{\sqrt{2}}} & \color{Red}{0} \\ \frac{1}{\sqrt{2}} & \color{Red}{ \frac{1}{\sqrt{2}}} & \color{Red}{0} \\0 & \color{Red}{0} & \color{Red}{1} \end{bmatrix}^T \end{align*}

Note,

• the left null space columns in $U$ are colored blue.
• the padded zero rows and columns in $\Sigma$ are colored gray.
• the null space columns in $V$ are colored red.

Reduced SVD

just remove the colored rows and columns, and it ends with reduced SVD.

\begin{align*} \begin{bmatrix} 1 & 1 & 0 \\ 2 & 2 & 0 \\ \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} \sqrt{10} \\ \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\0 \end{bmatrix}^T \end{align*}

Since A has only one positive singular value, we can't demonstrate truncated SVD with it.

Example 2

We use another example $B = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix}$ with $m=2$, $n=3$, and $r=2$ to show truncated SVD.

Full SVD:

\begin{align*} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{bmatrix} \begin{bmatrix} \sqrt{3} & 0 & \color{Gray}{0} \\ 0 & 1 & \color{Gray}{0} \\ \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} & \color{Red}{\frac{1}{\sqrt{3}}} \\ \frac{2}{\sqrt{6}} & 0 & \color{Red}{- \frac{1}{\sqrt{3}}} \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} & \color{Red}{\frac{1}{\sqrt{3}}} \end{bmatrix}^T \end{align*}

Reduced SVD:

\begin{align*} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{bmatrix} \begin{bmatrix} \sqrt{3} & 0 \\ 0 & 1 \\ \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} \\ \frac{2}{\sqrt{6}} & 0 \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} \end{bmatrix}^T \end{align*}

Truncated SVD:

\begin{align*} \begin{bmatrix} \frac{1}{2} & 1 & \frac{1}{2}\\ \frac{1}{2} & 1 & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} \sqrt{3} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{6}} \\ \frac{1}{\sqrt{6}} \\ \end{bmatrix}^T \end{align*}

Only the largest singular value $\sqrt{3}$ is taken. $\begin{bmatrix} \frac{1}{2} & 1 & \frac{1}{2}\\ \frac{1}{2} & 1 & \frac{1}{2} \end{bmatrix}$ is an approximation of the original $\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix}$.