Singular Value Decomposition

Singular Value Decomposition - SVD

The Singular Value Decomposition states that any matrix A (n x p) can be factored into A = UΣVᵀ where:

- U and V are orthogonal n x n matrices with orthogonal eigenvectors from AAᵀ and AᵀA. Vᵀ is a transposed matrix.

- Σ is a diagonal n x p matrix with the diagonal elements are ordered so that Σii ≥ Σjj for all i < j (descending order). These elements are the root of the positive eigenvalues of AAᵀ or Aᵀ A (AAᵀ and Aᵀ A have the same positive eigenvalues).

- uᵢ and vᵢ have unit length.

Example to find SVD of a matrix:

Applying A to a vector x (Ax = UΣVᵀx) can be visualized under geometry form.

Vᵀ represents a rotation or reflection of vectors.

Σ represents a linear dilation.

U represents a rotation or reflection.

Figure: geometry form of SVD

Another form of SVD:

σᵢ are descending order so more significant elements left side. Example:

We can use SVD for Dimensionality Reduction (just keep the important components). This can be applied when dataset has more features (columns) than observations (rows). This helps reduced dataset to a smaller number of features. If we select the top k largest singular values. An approximate B of the vector A: B = (UΣVᵀ)k

Example:

σ₂ is very small, we can ignore it.

Example: Dataset relation is y=2x, using SVD to reduce dataset.

from numpy import diag
from numpy import zeros
from scipy.linalg import svd
import numpy as np

# define a matrix
A = np.array([[1,2],[2,4],[3,6],[4,8]]).T

# Singular-value decomposition
U, s, VT = svd(A)
# create m x n Sigma matrix
Sigma = zeros((A.shape[0], A.shape[1]))
# populate Sigma with n x n diagonal matrix
Sigma[:A.shape[0], :A.shape[0]] = diag(s)
# select
n_elements = 1
Sigma = Sigma[:, :n_elements]
VT = VT[:n_elements, :]
# reconstruct
B = U.dot(Sigma.dot(VT))
print(B)
# transform
T = U.dot(Sigma)
print(T)