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