Singular Value Decomposition

The decomposition of any matrix into the product of an orthogonal matrix, a diagonal matrix with nonzero diagonal elements ranked from highest to lowest, and another orthogonal matrix.

Theorem

Let

• $A$ : $m\times n$ matrix
• $k$ : Rank of $A$

Let

• $U$ : $m\times m$ matrix
• $\Sigma$ : $m\times n$ matrix
• $V$ : $n\times n$ matrix

If

• $V=\left[\begin{array}{ccc}{\mathbf{v}}_1& \dots & {\mathbf{v}}_n\end{array}\right]$ orthogonally diagonalizes $A^{T}A$
• Nonzero diagonal entries of $\Sigma$ are ${\sigma }_1=\sqrt{{\lambda }_1}$, $\dots$, ${\sigma }_k=\sqrt{{\lambda }_k}$, where ${\lambda }_1,\dots ,{\lambda }_k$ are nonzero eigenvalues of $A^{T}A$ corresponding to the column vectors of $V$
• Column vectors of $V$ are ordered so that ${\sigma }_1\ge \cdots \ge {\sigma }_k>0$
• ${\mathbf{u}}_i=\frac{A{\mathbf{v}}_i}{||A{\mathbf{v}}_i||}=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i,i=1,2,\dots ,k$
• $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ is an orthonormal basis for $\mathrm{col}(A)$¹
• $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k,{\mathbf{u}}_{k+1},\dots ,{\mathbf{u}}_m\}$ is an extension of $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_k\}$ to an orthonormal basis for $R^m$

Then

$$\begin{array}{rl}A& =U\Sigma V^T\\ & =\left[\begin{array}{cccccccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_k& |& {\mathbf{u}}_{k+1}& \cdots & {\mathbf{u}}_m\end{array}\right]\left[\begin{array}{ccccc}{\sigma }_1& 0& \cdots & 0& \\ 0& {\sigma }_2& \cdots & 0& 0_{k\times (n-k)}\\ ⋮& ⋮& \ddots & ⋮& \\ 0& 0& \cdots & {\sigma }_k& \\ & 0_{(m-k)\times k}& & & 0_{(m-k)\times (n-k)}\end{array}\right]\left[\begin{array}{c}{\mathbf{v}}_1^T\\ {\mathbf{v}}_2^T\\ ⋮\\ {\mathbf{v}}_k^T\\ {\mathbf{v}}_{k+1}^T\\ ⋮\\ {\mathbf{v}}_n^T\end{array}\right]\end{array}$$

Procedure

To compute the SVD of an $m\times n$ matrix $A$ with rank $k$:

1. Compute $A^{T}A$ (an $n\times n$ symmetric matrix)

2. Find eigenvalues and eigenvectors of $A^{T}A$

   • Find all eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ of $A^{T}A$
   • Find corresponding eigenvectors for each eigenvalue

3. Normalize the eigenvectors

4. Order eigenvalues and eigenvectors

   • Order eigenvalues from largest to smallest: ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_k>0={\lambda }_{k+1}=\cdots ={\lambda }_n$
   • Order the corresponding unit eigenvectors accordingly to form $V=[{\mathbf{v}}_1{\mathbf{v}}_2\cdots {\mathbf{v}}_n]$

5. Construct $\Sigma$ (an $m\times n$ matrix)

   • Compute singular values: ${\sigma }_i=\sqrt{{\lambda }_i}$ for $i=1,2,\dots ,k$
   • Place ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_k$ on the diagonal
   • Fill remaining entries with zeros

6. Construct $U$ (an $m\times m$ matrix)

   • For $i=1,2,\dots ,k$: compute ${\mathbf{u}}_i=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i$
   • If $m>k$, extend $U$ with solution space of $A^T\mathbf{x}=0$
   • Form $U=[{\mathbf{u}}_1{\mathbf{u}}_2\cdots {\mathbf{u}}_m]$

7. (Optional) Verify: $A=U\Sigma V^T$

In short,

1. Descending sort normalized eigenvalues (${\sigma }_i^2$) & eigenvectors (${\mathbf{v}}_i$) of $A^{T}A$
2. $V=\left[\begin{array}{ccc}{\mathbf{v}}_i& \dots & {\mathbf{v}}_k\end{array}\right]$. If $n>k$,
3. $\Sigma =\mathrm{diag}({\sigma }_i),i=1,\dots ,k$
4. $U:{\mathbf{u}}_i=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i$
5. Column stack $U$ with $\mathrm{null}(A^T)$ if $k<m$

Tip

Based on Tranpose product rank theorem

$\mathrm{rank}(A^{T}A)=\mathrm{rank}(A)=k$

Based on Number of Nonzero Eigenvalues Theorem

$\mathrm{rank}(A)=k=\text{number of nonzero eigenvalues (counting multiplicity/duplicates)}$

Example

Let $A=\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& -1\end{array}\right]$

Step 1: Compute $A^{T}A$

$$\begin{array}{rl}{A}^{T}A& =\left[\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& -1\end{array}\right]\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& -1\end{array}\right]\\ & =\left[\begin{array}{ccc}2& 1& -1\\ 1& 2& 1\\ -1& 1& 2\end{array}\right]\end{array}$$

Step 2: Find eigenvalues and eigenvectors of $A^{T}A$

Finding eigenvalues:

$$\begin{array}{rl}\det (A^{T}A-\lambda I)& =\det \left[\begin{array}{ccc}2-\lambda & 1& -1\\ 1& 2-\lambda & 1\\ -1& 1& 2-\lambda \end{array}\right]=0\\ {\lambda }_1& =4,{\lambda }_2=2,{\lambda }_3=0\end{array}$$

Thus, $\mathrm{rank}(A)=k=2$

Finding eigenvectors:

For ${\lambda }_1=4$:

$$\begin{array}{rl}\left[\begin{array}{ccc}-2& 1& -1\\ 1& -2& 1\\ -1& 1& -2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\\ & \\ x_1& =x_3\\ x_2& =x_1\end{array}$$

For ${\lambda }_2=2$:

$$\begin{array}{rl}\left[\begin{array}{ccc}0& 1& -1\\ 1& 0& 1\\ -1& 1& 0\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\\ & \\ x_2& =x_3\\ x_1& =-x_3\end{array}$$

For ${\lambda }_3=0$:

$$\begin{array}{rl}\left[\begin{array}{ccc}2& 1& -1\\ 1& 2& 1\\ -1& 1& 2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\\ & \\ x_1& =-x_3\\ x_2& =x_3\end{array}$$

Suppose $x_1=1$ for ${\lambda }_1$, $x_3=1$ for ${\lambda }_2$ and ${\lambda }_3$. The unnormalized eigenvectors are:

$$\begin{array}{rl}{\mathbf{w}}_1& =\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]\\ {\mathbf{w}}_2& =\left[\begin{array}{c}-1\\ 1\\ 1\end{array}\right]\\ {\mathbf{w}}_3& =\left[\begin{array}{c}-1\\ 1\\ 1\end{array}\right]\end{array}$$

Step 3: Normalize the eigenvectors to unit length

For ${\lambda }_1=4$

$$\begin{array}{rl}\Vert {\mathbf{w}}_1\Vert & =\sqrt{1^2+1^2+1^2}=\sqrt{3}\\ {\mathbf{v}}_1& =\frac{1}{\sqrt{3}}\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\end{array}\right]\end{array}$$

For ${\lambda }_2=2$

$$\begin{array}{rl}\Vert {\mathbf{w}}_2\Vert & =\sqrt{(-1{)}^2+1^2+1^2}=\sqrt{3}\\ {\mathbf{v}}_2& =\frac{1}{\sqrt{3}}\left[\begin{array}{c}-1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}-\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\end{array}\right]\end{array}$$

For ${\lambda }_3=0$

$$\begin{array}{rl}\Vert {\mathbf{w}}_3\Vert & =\sqrt{(-1{)}^2+1^2+1^2}=\sqrt{3}\\ {\mathbf{v}}_3& =\frac{1}{\sqrt{3}}\left[\begin{array}{c}-1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}-\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\end{array}\right]\end{array}$$

Step 4: Order eigenvalues and eigenvectors

$$V=\left[\begin{array}{ccc}{\mathbf{v}}_1& {\mathbf{v}}_2& {\mathbf{v}}_3\end{array}\right]=\left[\begin{array}{ccc}\frac{1}{\sqrt{3}}& -\frac{1}{\sqrt{3}}& -\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}\end{array}\right]$$

Step 5: Construct $\Sigma$

$$\begin{array}{rl}{\sigma }_1& =\sqrt{{\lambda }_1}=2\\ {\sigma }_2& =\sqrt{{\lambda }_2}=\sqrt{2}\\ {\sigma }_3& =\sqrt{{\lambda }_3}=0\\ & \\ \Sigma & =\left[\begin{array}{ccc}2& 0& 0\\ 0& \sqrt{2}& 0\\ 0& 0& 0\end{array}\right]\end{array}$$

Step 6: Construct $U$

For $i=1,2$: compute ${\mathbf{u}}_i=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i$

For $i=1$

$$\begin{array}{rl}{\mathbf{u}}_1& =\frac{1}{2}\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& -1\end{array}\right]\left[\begin{array}{c}\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\end{array}\right]\\ & =\frac{1}{2}\left[\begin{array}{c}\frac{2}{\sqrt{3}}\\ \frac{2}{\sqrt{3}}\\ 0\end{array}\right]\\ & =\left[\begin{array}{c}\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ 0\end{array}\right]\end{array}$$

For $i=2$

$$\begin{array}{rl}{\mathbf{u}}_2& =\frac{1}{\sqrt{2}}\left[\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& -1\end{array}\right]\left[\begin{array}{c}-\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\end{array}\right]\\ & =\frac{1}{\sqrt{2}}\left[\begin{array}{c}0\\ \frac{2}{\sqrt{3}}\\ -\frac{2}{\sqrt{3}}\end{array}\right]\\ & =\left[\begin{array}{c}0\\ \sqrt{\frac{2}{3}}\\ -\sqrt{\frac{2}{3}}\end{array}\right]\end{array}$$

Notice that $3=m>k=2$. Thus we extend $U$ with $\mathrm{null}(A^T)$:

Find ${\mathbf{u}}_3$ in $\mathrm{null}(A^T)$:

$$\begin{array}{rl}{A}^T\mathbf{x}& =0\\ \left[\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& -1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]& =\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]\\ & \\ x_1+x_3& =0\\ x_1+x_2& =0\\ x_2-x_3& =0\end{array}$$

So $x_3=-x_1$, $x_2=-x_1$. Suppose $x_1=1$

Unnormalized vector: $\mathbf{x}=\left[\begin{array}{c}1\\ -1\\ -1\end{array}\right]$

$$\begin{array}{rl}\Vert {\mathbf{u}}_3\Vert & =\sqrt{1^2+(-1{)}^2+(-1{)}^2}=\sqrt{3}\\ {\mathbf{u}}_3& =\frac{1}{\sqrt{3}}\left[\begin{array}{c}1\\ -1\\ -1\end{array}\right]=\left[\begin{array}{c}\frac{1}{\sqrt{3}}\\ -\frac{1}{\sqrt{3}}\\ -\frac{1}{\sqrt{3}}\end{array}\right]\end{array}$$

Therefore

$$U=\left[\begin{array}{ccc}{\mathbf{u}}_1& {\mathbf{u}}_2& {\mathbf{u}}_3\end{array}\right]=\left[\begin{array}{ccc}\frac{1}{\sqrt{3}}& 0& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}& \sqrt{\frac{2}{3}}& -\frac{1}{\sqrt{3}}\\ 0& -\sqrt{\frac{2}{3}}& -\frac{1}{\sqrt{3}}\end{array}\right]$$

Step 7: Verify

$$A=U\Sigma V^T=\left[\begin{array}{ccc}\frac{1}{\sqrt{3}}& 0& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}& \sqrt{\frac{2}{3}}& -\frac{1}{\sqrt{3}}\\ 0& -\sqrt{\frac{2}{3}}& -\frac{1}{\sqrt{3}}\end{array}\right]\left[\begin{array}{ccc}2& 0& 0\\ 0& \sqrt{2}& 0\\ 0& 0& 0\end{array}\right]\left[\begin{array}{ccc}\frac{1}{\sqrt{3}}& -\frac{1}{\sqrt{3}}& -\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{3}}\end{array}\right]$$

Related theorems

Eigenvalues of $X^{T}X$ and $X{X}^T$

Let $X$ be an $m\times n$ matrix.

The nonzero eigenvalues of $X^{T}X$ and $X{X}^T$ are identical.

Note

This explains why we can compute SVD using either $X^{T}X$ or $X{X}^T$ - they share the same nonzero eigenvalues, which determine the singular values.

Existence of SVD

Let $X$ be an $m\times n$ matrix with $\mathrm{rank}(X)=s\le n$.

Then $X$ can be written as:

$$X=L^T\left[\begin{array}{cc}{\Lambda }^{1/2}& 0\\ 0& 0\end{array}\right]M^T$$

where:

• $L$ and $M$ are orthogonal matrices
• $\Lambda$ is a diagonal matrix containing the nonzero eigenvalues of $X{X}^T$ or $X^{T}X$, ordered from largest to smallest

Note

This is equivalent to the standard SVD form $X=U\Sigma V^T$, where $U=L^T$, $\Sigma =\left[\begin{array}{cc}{\Lambda }^{1/2}& 0\\ 0& 0\end{array}\right]$, and $V^T=M^T$.

Rank and Nonzero Eigenvalues

For any matrix $X$:

$$\mathrm{rank}(X)=\text{number of nonzero eigenvalues of }{X}^{T}X\text{ (or }X{X}^T\text{)}$$

Equivalently, the column rank and row rank equal the number of nonzero singular values.

Note

This connects Rank to eigenvalues through SVD, providing a computational method for determining rank.

Rank of Kronecker Product

Let $A$ be an $m\times n$ matrix and $B$ be a $p\times q$ matrix.

Then:

$$\mathrm{rank}(A\otimes B)=\mathrm{rank}(A)\times \mathrm{rank}(B)$$

where $\otimes$ denotes the Kronecker product.

Non-negative Definite Characterization

Let $A$ be an $n\times n$ symmetric matrix.

Then $A$ is positive semidefinite if and only if:

$$\mathrm{tr}(AB)\ge 0$$

for all positive semidefinite matrices $B$.

where $\mathrm{tr}(\cdot )$ denotes the trace of a matrix.

Rayleigh Quotient Bounds

Let $A$ be an $m\times m$ Positive Semidefinite Matrix with nonzero eigenvalues ordered as ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_s>0$.

For any nonzero vector $\mathbf{x}\in {\mathbb{R}}^m$:

Case 1: If $s=m$ (full rank):

$${\lambda }_s\le \frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}\le {\lambda }_1$$

Case 2: If $s<m$ (rank deficient):

$$0\le \frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}\le {\lambda }_1$$

Note

The quantity $\frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}$ is called the Rayleigh quotient. This theorem shows that:

• The largest eigenvalue ${\lambda }_1$ is the maximum value of the Rayleigh quotient
• The smallest nonzero eigenvalue ${\lambda }_s$ is the minimum value (when $A$ is full rank)
• When $A$ is rank deficient, the Rayleigh quotient can reach 0

Code implementation

import numpy as np
from scipy.linalg import null_space
 
np.set_printoptions(precision=2, suppress=True)
 
 
A = np.array([
    [2, 3],
    [4, 5],
    [6, 7]
])
 
print(f"{A=}")
#|| <jIh\n\n{k=}laa2rII|bCEGstAtvo>
 
k = int(np.linalg.matrix_rank(A))
m, n = A.shape
 
ATA = A.T @ A
 
eigval, eigvec = np.linalg.eig(ATA)
 
# Descending sort
idx = np.argsort(eigval)[::-1]
eigval_sorted = eigval[idx]
V = eigvec[:, idx]
sigma = np.sqrt(eigval_sorted[:k])
 
Sigma = np.zeros((m, n))
Sigma[:k, :k] = np.diag(sigma)
 
U_k = np.column_stack([A @ V[:, i] / sigma[i] for i in range(k)])
if k < m:
    U = np.column_stack([U_k, null_space(A.T)])
else:
    U = U_k
 
 
#|| <bCEGstAtvo|gnwb7rDeUd>
 
print(U @ Sigma @ V.T)
print(A)
print(np.allclose(A, U @ Sigma @ V.T))

Footnotes

1. Column Space ↩