Unit 08

Matrix Decompositions for Machine Learning

breaking matrices into fundamental components for analysis and computation

Core Concepts Covered

Eigenvalues, eigenvectors, and spectral decomposition
Singular Value Decomposition (SVD) and low-rank approximation
Principal Component Analysis (PCA) for dimensionality reduction

Local Setup Recommendation

To execute and experiment with the code cells below on your local machine, ensure you have set up your isolated virtual environments and scientific libraries by following the detailed protocols in Unit 03: Environment Setup or run them in Google Colab.

1. Eigenvalues, Eigenvectors, and Spectral Decomposition

Just as integers can be factored into prime numbers (e.g., $15 = 3 \times 5$ ), matrices can be decomposed into fundamental vector and scaling components. This allows us to analyze the structural properties of complex linear transformations.

An Eigenvector of a square matrix $A$ is a special non-zero vector $v$ such that multiplying $A$ by $v$ only scales the vector, without changing its geometric direction. This scaling factor is called the Eigenvalue $\lambda$ . Mathematically, this is written as:

$Av = \lambda v$

The Stretching Sheet Analogy: Imagine taking a square rubber sheet and stretching it diagonally. Most points on the sheet move in new directions. However, points lying along the exact diagonal line of the stretch continue to point in the exact same direction; they have only been pulled further apart. This diagonal line represents the Eigenvector of the stretching transformation, and the amount of stretch represents its Eigenvalue.

If a matrix $A$ is symmetric ( $A = A^T$ ), we can perform Spectral Decomposition. This factors the matrix into an orthogonal basis of eigenvectors and a diagonal matrix of eigenvalues:

$A = Q \Lambda Q^T$

where $Q$ is an orthogonal matrix whose columns are the eigenvectors of $A$ , and $\Lambda$ (Lambda) is a diagonal matrix containing the corresponding eigenvalues. We use eigenvalues to measure the scale of variance along specific vector directions.

Spectral Reconstruction A = QΛQᵀ

Read diagram labels

Q
rotate
Λ
scale
Qᵀ
rotate back
×

Jupyter Code Notebook Cell

Python 3 (ipykernel)

In [1]:

import numpy as np

# Create a symmetric matrix A
A = np.array([[4, 2], [2, 4]])

# Compute eigenvalues and eigenvectors
eigenvalues, eigenvectors = np.linalg.eig(A)

print("Eigenvalues:", eigenvalues)
# Columns of eigenvectors correspond to eigenvectors
print("Eigenvector Matrix:\n", eigenvectors)

# Verify Av = lambda v for the first eigenvector
v0 = eigenvectors[:, 0]
lambda0 = eigenvalues[0]
print("Av0:", A @ v0)
print("lambda0 * v0:", lambda0 * v0)
print("Av0 equals lambda0 * v0:", np.allclose(A @ v0, lambda0 * v0))

Out [1]:

Eigenvalues: [6. 2.]
Eigenvector Matrix:
 [[ 0.70710678 -0.70710678]
 [ 0.70710678  0.70710678]]
Av0: [4.24264069 4.24264069]
lambda0 * v0: [4.24264069 4.24264069]
Av0 equals lambda0 * v0: True

Worked Example 1

Solve and Reconstruct a Small Eigensystem

Problem

Find the eigensystem of $A=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ and state its spectral reconstruction.

Step-by-step solution

1. $\det(A-\lambda I)=(2-\lambda)^2-1=(\lambda-3)(\lambda-1)$ , so the eigenvalues are $3$ and $1$ .

2.Normalized eigenvectors are $v_1=(1,1)^T/\sqrt{2}$ and $v_2=(1,-1)^T/\sqrt{2}$ .

Final answer and interpretation

With $Q=[v_1\ v_2]$ and $\Lambda=\operatorname{diag}(3,1)$ , multiplication verifies $A=Q\Lambda Q^T$ .

2. Singular Value Decomposition (SVD)

While eigensystem decompositions are mathematically restricted strictly to square matrices, Singular Value Decomposition (SVD) is a highly robust factorization that works on any rectangular matrix $A \in \mathbb{R}^{m \times n}$ (such as a table with $m$ samples and $n$ features).

SVD decomposes $A$ into three matrices:

$A = U \Sigma V^T$

• $U \in \mathbb{R}^{m \times m}$ : An orthogonal matrix containing the left-singular vectors of $A$ (which represent eigenvectors of $A A^T$ ).

• $\Sigma \in \mathbb{R}^{m \times n}$ : A diagonal matrix containing positive singular values $\sigma_i$ sorted in descending order of magnitude.

• $V^T \in \mathbb{R}^{n \times n}$ : The transpose of an orthogonal matrix containing the right-singular vectors of $A$ (which represent eigenvectors of $A^T A$ ).

The compact rank- $r$ form uses $U_r\in\mathbb{R}^{m\times r}$ , $\Sigma_r\in\mathbb{R}^{r\times r}$ , and $V_r^T\in\mathbb{R}^{r\times n}$ . Keeping only the largest $k$ singular values produces the best rank- $k$ approximation under the Frobenius norm.

The Movie Recommender Example: Rows can represent users and columns movies. A truncated SVD compresses the grid into user factors, factor strengths, and movie factors; discarded small singular directions often contain noise.

Compact SVD Shape Decomposition

Read diagram labels

U
m × r
Σ
r × r
Vᵀ
r × n
×

Worked Example 1

SVD Shape Trace

Problem

A matrix has shape $120\times30$ and rank $20$ . Give its compact-SVD shapes and the factor shapes for a rank-5 reconstruction.

Step-by-step solution

1. $U_r$ is $120\times20$ , $\Sigma_r$ is $20\times20$ , and $V_r^T$ is $20\times30$ .

2.For $k=5$ , the product is $(120\times5)(5\times5)(5\times30)$ .

Final answer and interpretation

The reconstruction remains $120\times30$ , but uses only five singular directions.

Worked Example 2

Rank- $k$ Reconstruction Error

Problem

If singular values are $(5,3,1)$ , find the Frobenius errors of the best rank-1 and rank-2 approximations.

Step-by-step solution

1.The squared truncation error is the sum of squared discarded singular values.

2. $\|A-A_1\|_F=\sqrt{3^2+1^2}=\sqrt{10}$ .

Final answer and interpretation

$\|A-A_2\|_F=\sqrt{1^2}=1$ .

3. Dimensionality Reduction & Principal Component Analysis (PCA)

In high-dimensional datasets, features are often highly redundant (for instance, house area in square feet vs. square meters). We use Principal Component Analysis (PCA) to reduce dataset dimensions while retaining as much variance (information) as possible.

To perform PCA on a dataset matrix $X$ :

1. Zero-center the data by subtracting the mean of each feature: $X_0 = X - \mu$ .

2. Compute the Covariance Matrix: $\Sigma_0 = \frac{1}{n} X_0^T X_0$ . This matrix measures how all features vary together.

3. Compute the Eigensystem: Find the eigenvectors and eigenvalues of the covariance matrix $\Sigma_0$ . The eigenvector corresponding to the largest eigenvalue is the First Principal Component, the axis in coordinate space along which the data is most spread out (maximum variance).

4. Project: Project centered coordinates onto the leading eigenvectors. The explained-variance ratio of component $j$ is $\lambda_j/\sum_i\lambda_i$ .

PCA Projects Data onto Principal Axes

Read diagram labels

X₀
n × d
Wₖ
d × k
Z
n × k
×

Worked Example 1

PCA from Centering to Projection

Problem

For points $(1,1),(2,2),(3,3)$ , find the first principal direction, projected coordinates, and explained variance.

Step-by-step solution

1.The mean is $(2,2)$ ; centered rows are $(-1,-1),(0,0),(1,1)$ .

2.With divisor $n-1=2$ , the covariance is $\begin{bmatrix}1&1\\1&1\end{bmatrix}$ , whose eigenvalues are $2$ and $0$ .

3.The first direction is $(1,1)^T/\sqrt{2}$ and the projections are $(-\sqrt{2},0,\sqrt{2})$ .

Final answer and interpretation

Its explained-variance ratio is $2/(2+0)=100\%$ .

Worked Example 2

Cumulative Component Choice

Problem

If PCA eigenvalues are $(9,4,1)$ , how many components retain at least $90\%$ of the variance?

Step-by-step solution

1.Total variance is $14$ .

2.One component retains $9/14\approx64.3\%$ ; two retain $13/14\approx92.9\%$ .

Final answer and interpretation

Choose two components.

Interactive Practice Quiz

Test your understanding with instant feedback

QUESTION 01

Which of the following describes the definition of an Eigenvector $v$ and Eigenvalue $\lambda$ for a matrix $A$ ?

QUESTION 02

Why is Singular Value Decomposition (SVD) preferred over Eigensystem decomposition for general-purpose dataset matrices?

QUESTION 03

In SVD decomposition $A = U \Sigma V^T$ , what does the diagonal matrix $\Sigma$ contain?

QUESTION 04

In Principal Component Analysis (PCA), the principal components are calculated as the eigenvectors of which matrix?

QUESTION 05

How do we compress data using SVD low-rank approximations?

QUESTION 06

If a matrix $A \in \mathbb{R}^{d \times d}$ is symmetric ( $A = A^T$ ), which of the following properties must its eigenvalues and eigenvectors satisfy?

QUESTION 07

In Spectral Decomposition $A = Q \Lambda Q^T$ , what does the diagonal matrix $\Lambda$ represent?

QUESTION 08

For a dataset with $n$ samples and $d$ features, the dimension of the right-singular vector matrix $V^T$ in SVD is:

QUESTION 09

Which of the following describes the first step of Principal Component Analysis (PCA)?

QUESTION 10

Matrix Decompositions for Machine Learning

Core Concepts Covered

Local Setup Recommendation

1. Eigenvalues, Eigenvectors, and Spectral Decomposition

Solve and Reconstruct a Small Eigensystem

2. Singular Value Decomposition (SVD)

SVD Shape Trace

Rank- $k$ Reconstruction Error

3. Dimensionality Reduction & Principal Component Analysis (PCA)

PCA from Centering to Projection

Cumulative Component Choice

Interactive Practice Quiz

Which of the following describes the definition of an Eigenvector $v$ and Eigenvalue $\lambda$ for a matrix $A$ ?

Why is Singular Value Decomposition (SVD) preferred over Eigensystem decomposition for general-purpose dataset matrices?

In SVD decomposition $A = U \Sigma V^T$ , what does the diagonal matrix $\Sigma$ contain?

In Principal Component Analysis (PCA), the principal components are calculated as the eigenvectors of which matrix?

How do we compress data using SVD low-rank approximations?

If a matrix $A \in \mathbb{R}^{d \times d}$ is symmetric ( $A = A^T$ ), which of the following properties must its eigenvalues and eigenvectors satisfy?

In Spectral Decomposition $A = Q \Lambda Q^T$ , what does the diagonal matrix $\Lambda$ represent?

For a dataset with $n$ samples and $d$ features, the dimension of the right-singular vector matrix $V^T$ in SVD is:

Which of the following describes the first step of Principal Component Analysis (PCA)?

The first principal component axis extracted during PCA represents:

Further Readings

Matrix Decompositions for Machine Learning

Core Concepts Covered

Local Setup Recommendation

1. Eigenvalues, Eigenvectors, and Spectral Decomposition

Solve and Reconstruct a Small Eigensystem

2. Singular Value Decomposition (SVD)

SVD Shape Trace

Rank-kkk Reconstruction Error

3. Dimensionality Reduction & Principal Component Analysis (PCA)

PCA from Centering to Projection

Cumulative Component Choice

Interactive Practice Quiz

Which of the following describes the definition of an Eigenvector vvv and Eigenvalue λ\lambdaλ for a matrix AAA?

Why is Singular Value Decomposition (SVD) preferred over Eigensystem decomposition for general-purpose dataset matrices?

In SVD decomposition A=UΣVTA = U \Sigma V^TA=UΣVT, what does the diagonal matrix Σ\SigmaΣ contain?

In Principal Component Analysis (PCA), the principal components are calculated as the eigenvectors of which matrix?

How do we compress data using SVD low-rank approximations?

If a matrix A∈Rd×dA \in \mathbb{R}^{d \times d}A∈Rd×d is symmetric (A=ATA = A^TA=AT), which of the following properties must its eigenvalues and eigenvectors satisfy?

In Spectral Decomposition A=QΛQTA = Q \Lambda Q^TA=QΛQT, what does the diagonal matrix Λ\LambdaΛ represent?

For a dataset with nnn samples and ddd features, the dimension of the right-singular vector matrix VTV^TVT in SVD is:

Which of the following describes the first step of Principal Component Analysis (PCA)?

The first principal component axis extracted during PCA represents:

Further Readings

Rank- $k$ Reconstruction Error

Which of the following describes the definition of an Eigenvector $v$ and Eigenvalue $\lambda$ for a matrix $A$ ?

In SVD decomposition $A = U \Sigma V^T$ , what does the diagonal matrix $\Sigma$ contain?

If a matrix $A \in \mathbb{R}^{d \times d}$ is symmetric ( $A = A^T$ ), which of the following properties must its eigenvalues and eigenvectors satisfy?

In Spectral Decomposition $A = Q \Lambda Q^T$ , what does the diagonal matrix $\Lambda$ represent?

For a dataset with $n$ samples and $d$ features, the dimension of the right-singular vector matrix $V^T$ in SVD is: