Singular Value Decomposition (SVD)

By /

Introduction

Singular Value Decomposition (SVD) is a matrix factorization technique that is widely used in linear algebra, statistics, signal processing, and machine learning.

Let $A$ be any matrix of order $m \times n$. $A \in \mathbb{R}^{m \times n}$. Then SVD of $A$ is

$$ A = U \Sigma V^T $$

Where:

  • $A$ is an $m \times n$ matrix.
  • $U$ is an $m \times m$ orthogonal matrix. The columns of $U$ ( ie,$U^TU = I_m$) are the left singular vectors of $A$.
  • $\Sigma$ is an $m \times n$ diagonal matrix with non-negative real numbers on the diagonal. These are the singular values ($\sigma_i$) of $A$, arranged in decreasing order. $\sigma_i = \sqrt{\lambda_i}$, where $\lambda_i$ : eigen values of $A^TA$
  • $V^T$ is an $n \times n$ orthogonal matrix. The rows of $V^T$ (or columns of $V$ (ie, $V^TV = I_n$)) are the right singular vectors of $A$.

Properties of SVD:

  • The matrices $U$ and $V$ are orthogonal, meaning:
  • $U^T U = I_m$ (where $I_m$ is the identity matrix of size $m$),
  • $V^T V = I_n$ (where $I_n$ is the identity matrix of size $n$).
  • The singular values in $\Sigma$ are non-negative and typically arranged in decreasing order.
  • The singular value decomposition can be thought of as a way to orthogonally transform the matrix $A$ into a form where its action is separated into scaling along orthogonal directions.

Mathematical Treatment of SVD

Geometric Interpretation of SVD

1. Right Singular Vectors ($V$): These vectors define the directions of the axes in the input space where the transformation $A$ acts.

2. Singular Values ($\Sigma$): These represent the scaling factors along these new axes. They indicate how much stretching or shrinking occurs in the direction of each right singular vector.

3. Left Singular Vectors ($U$): These vectors define the directions in the output space of the transformation $A$.

Deriving SVD

To derive the SVD for a matrix $A \in \mathbb{R}^{m \times n}$, we need to compute the eigenvalues and eigenvectors of the matrices $A^T A$ and $A A^T$.

  1. Find $A^T A$ and $AA^T$
  2. Compute the eigenvalues ($\lambda_i$) and eigen vectors ($v_i$) of $A^T A$ and $AA^T$
  3. The square roots of the non-zero eigenvalues ($\sqrt{\lambda_i}$) of $A^T A$ are the singular values of $A$, which are placed on the diagonal of $\Sigma$ in descending order $\sigma_1 \ge \sigma_2 \ge \cdots$.
  4. Normalized eigenvectors of $A^T A$ form the columns of $V$
  5. Normalized eigenvectors ($u_i$) of $AA^T$ form the columns of $U$ where, $ u_i = \frac{A v_i}{\sigma_i} $

Singular Values

The diagonal elements of $\Sigma$, denoted $\sigma_1, \sigma_2, \dots, \sigma_r$ (where $r = \min(m, n)$), are the square roots of the non-zero eigenvalues of $A^T A$ or $A A^T$. These values are typically arranged in decreasing order.

Full SVD

For the full SVD, the matrices $U$ and $V$ are square and orthogonal:

  • $U$ is an $m \times m$ orthogonal matrix.
  • $\Sigma$ is an $m \times n$ diagonal matrix (with zeros padding the non-square part).
  • $V^T$ is an $n \times n$ orthogonal matrix.

The full SVD is represented as:

$$ A = U \Sigma V^T $$

$A$ is Real symmetric

Eigen decomposition, SVD are almost coincide.

For SVD, $V$ is eigen vectors of $A^TA$. But if $A$ is symmetric $A^TA = AA = A^2$

$\therefore$ $V$’s eigen values of $A^TA$ is based on eigen values of $A^2$ which $\lambda^2$ square of eigen values of $A$.

Also, hence $\Sigma$ which is singular values of $A^TA$ which is square root of eigen values of $A^TA$

$\Rightarrow$ Singular values of $A^TA$

$$= \sqrt{\text{Eigen values of } A^TA}$$

$$= \sqrt{\text{Eigen values of } A^2}$$

$$= \sqrt{\lambda^2} = |\lambda|$$

So, for a real symmetric, $U = V = Q$ (orthonormal eigen vectors)

$$\Sigma = \text{diag}(|\lambda_i|).$$

Example 1:

Consider a $2 \times 3$ matrix

$$ A = \begin{bmatrix} 1 & 0 & -1\\ 0 & 1 & 0 \end{bmatrix} $$

We compute the SVD as follows:

1. Compute $A^T A$,$AA^T$:

$$ A^T A = \begin{bmatrix} 1 & 0 & -1 \\ 0 & 1 & 0 \\ -1 & 0 & 1\end{bmatrix} $$

$$ A A^T = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} $$

2. Find the eigenvalues and eigenvectors of $AA^T$, $A^T A$.

Eigenvalues of $AA^T$ are $2,1$ with eigen vectors: $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$

Eigenvalues of $A^TA$ are $2,1,0$ with eigen vectors: $\begin{bmatrix} 1 \\ 0 \\ -1\end{bmatrix}$;   $\begin{bmatrix} 0 \\ 1 \\0 \end{bmatrix}$ and $\begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$

3. Normalized Eigen vectors

For $AA^T$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$

For $A^TA$, $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ \frac{-1}{\sqrt{2}}\end{bmatrix}$;   $\begin{bmatrix} 0 \\ 1 \\0 \end{bmatrix}$ and $\begin{bmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ \frac{1}{\sqrt{2}}\end{bmatrix}$

4. Form the matrix $U$, whose columns are normalized eigen vecgors of $AA^T$

5. Form the matrix $V$, whose columns are normalized eigen vecgors of $A^TA$

6. Compute the positive square roots of the non-zero eigenvalues of $A^TA$ to get the singular values for forming the matrix $\Sigma$. Diagonal elements of $\Sigma$ are the non-zerosingular values (2, 1). All other places are zero

That is,

   $$\Sigma=\begin{bmatrix} \sqrt{2} & 0 & 0\\ 0 & 1 & 0 \end{bmatrix}$$

Finally, construct the full SVD:

$$ A = U \Sigma V^T $$

Practice

$$1. A=\begin{bmatrix} 1 & -2 & 0\\ 0 & -2 & 1 \end{bmatrix}$$

$$2. A=\begin{bmatrix} 3 & 2 & 2\\ 2 & 3 & -2 \end{bmatrix}$$

$$3. A=\begin{bmatrix} 2 & 3\\ 4 & 10 \end{bmatrix}$$

Scroll to Top