Solved Exercises on Singular Value Decomposition (SVD) Introduction in Linear Algebra

Master SVD: singular values, left/right singular vectors, and matrix factorization through these 5 detailed exercises.

SVD Fundamentals
\(A = U\Sigma V^T\)
SVD Formula
Key Definitions:

SVD: Any m×n matrix A can be factored as A = UΣV^T where U and V are orthogonal matrices and Σ is diagonal

Singular Values σᵢ: Square roots of eigenvalues of A^T A (or AA^T), arranged in descending order

Left Singular Vectors uᵢ: Orthonormal eigenvectors of AA^T

Right Singular Vectors vᵢ: Orthonormal eigenvectors of A^T A

SVD Computation Process:
  1. Compute A^T A: Find eigenvalues and eigenvectors
  2. Find singular values: σᵢ = √λᵢ where λᵢ are eigenvalues of A^T A
  3. Find right singular vectors: vᵢ are normalized eigenvectors of A^T A
  4. Find left singular vectors: uᵢ = (1/σᵢ)Avᵢ
  5. Form matrices: U from left vectors, Σ from singular values, V from right vectors
Tip 1: Singular values are always non-negative and ordered σ₁ ≥ σ₂ ≥ ... ≥ σᵣ > 0
Tip 2: Rank of A equals number of non-zero singular values
Tip 3: A^T A and AA^T have the same non-zero eigenvalues
Tip 4: Use SVD for low-rank approximation and noise reduction
Key Properties: U^T U = I, V^T V = I, Σ is rectangular diagonal, exists for any matrix
Applications: Image compression, recommendation systems, data analysis, dimensionality reduction
Essential Formulas:

• SVD: A = UΣV^T

• Singular values: σᵢ = √λᵢ(A^T A)

• Left singular vectors: uᵢ = (1/σᵢ)Avᵢ

• Matrix norm: ||A||₂ = σ₁

Solution: Exercises 1 to 3
1 Basic SVD
Exercise 1
Find the SVD of: A =
[
3
0
4
0
]
Definition:

SVD Decomposition: Express A as A = UΣV^T where U and V are orthogonal and Σ is diagonal

Step-by-step Method:
  1. Compute A^T A
  2. Find eigenvalues and eigenvectors of A^T A
  3. Calculate singular values σᵢ = √λᵢ
  4. Find right singular vectors vᵢ
  5. Find left singular vectors uᵢ = (1/σᵢ)Avᵢ
  6. Form U, Σ, and V matrices
Step 1: Compute A^T A

A^T A =

[
3
4
0
0
]
[
3
0
4
0
]
=
[
25
0
0
0
]

Step 2: Find eigenvalues of A^T A

det(A^T A - λI) = det

[
25-λ
0
0
-λ
]
= (25-λ)(-λ) = 0

Therefore: λ₁ = 25, λ₂ = 0

Step 3: Find singular values

σ₁ = √λ₁ = √25 = 5, σ₂ = √λ₂ = √0 = 0

Step 4: Find right singular vectors

For λ₁ = 25: (A^T A - 25I)v = 0 →

[
0
0
0
-25
]
[
x
y
]
=
[
0
0
]

This gives y = 0, so v₁ =

[
1
0
]

For λ₂ = 0: (A^T A)v = 0 →

[
25
0
0
0
]
[
x
y
]
=
[
0
0
]

This gives x = 0, so v₂ =

[
0
1
]

Step 5: Find left singular vectors

u₁ = (1/σ₁)Av₁ = (1/5)

[
3
0
4
0
]
[
1
0
]
= (1/5)
[
3
4
]
=
[
3/5
4/5
]

For u₂, we need a unit vector orthogonal to u₁. We can choose u₂ =

[
-4/5
3/5
]

A = UΣV^T where U =
[
3/5
-4/5
4/5
3/5
]
, Σ =
[
5
0
0
0
]
, V =
[
1
0
0
1
]
Final answer:

A = UΣV^T with one non-zero singular value

Applied rules:

• SVD computation: Systematic approach to factor any matrix

• Rank: Number of non-zero singular values equals rank

• Orthogonality: U and V are orthogonal matrices

2 Full Rank SVD
Exercise 2
Find the SVD of: A =
[
1
1
0
1
]
Definition:

Full Rank SVD: When A has full column rank, all singular values are non-zero

Step 1: Compute A^T A

A^T A =

[
1
0
1
1
]
[
1
1
0
1
]
=
[
1
1
1
2
]

Step 2: Find eigenvalues of A^T A

det(A^T A - λI) = det

[
1-λ
1
1
2-λ
]

= (1-λ)(2-λ) - 1 = 2 - 3λ + λ² - 1 = λ² - 3λ + 1

Using quadratic formula: λ = (3 ± √(9-4))/2 = (3 ± √5)/2

So λ₁ = (3 + √5)/2 ≈ 2.618, λ₂ = (3 - √5)/2 ≈ 0.382

Step 3: Find singular values

σ₁ = √λ₁ = √((3 + √5)/2) ≈ 1.618, σ₂ = √λ₂ = √((3 - √5)/2) ≈ 0.618

Step 4: Find right singular vectors

For λ₁ = (3 + √5)/2: (A^T A - λ₁I)v = 0

[
1-(3+√5)/2
1
1
2-(3+√5)/2
]
=
[
(-1-√5)/2
1
1
(1-√5)/2
]

Row 1: ((-1-√5)/2)x + y = 0, so y = ((1+√5)/2)x

Normalizing: v₁ = (1/√(1 + ((1+√5)/2)²))

[
1
(1+√5)/2
]
≈
[
0.526
0.851
]

For λ₂ = (3 - √5)/2: Similarly, v₂ ≈

[
0.851
-0.526
]

Step 5: Find left singular vectors

u₁ = (1/σ₁)Av₁ ≈ (1/1.618)

[
1
1
0
1
]
[
0.526
0.851
]
≈
[
0.851
0.526
]

u₂ = (1/σ₂)Av₂ ≈ (1/0.618)

[
1
1
0
1
]
[
0.851
-0.526
]
≈
[
0.526
-0.851
]

U ≈
[
0.851
0.526
0.526
-0.851
]
, Σ ≈
[
1.618
0
0
0.618
]
, V ≈
[
0.526
0.851
0.851
-0.526
]
Final answer:

A = UΣV^T with both singular values non-zero (full rank)

Applied rules:

• Full rank: All singular values are positive

• Condition number: Ratio of largest to smallest singular value

• Accuracy: Exact symbolic values preferred over approximations

3 Verification Exercise
Exercise 3
Verify that the matrices U, Σ, and V from Exercise 1 satisfy A = UΣV^T
Definition:

Verification: Confirm SVD by computing UΣV^T and comparing to A

Step 1: Recall matrices from Exercise 1

U =

[
3/5
-4/5
4/5
3/5
]
, Σ =
[
5
0
0
0
]
, V =
[
1
0
0
1
]

Step 2: Compute V^T

V^T =

[
1
0
0
1
]
(since V is identity)

Step 3: Compute ΣV^T

ΣV^T =

[
5
0
0
0
]
[
1
0
0
1
]
=
[
5
0
0
0
]

Step 4: Compute U(ΣV^T)

UΣV^T =

[
3/5
-4/5
4/5
3/5
]
[
5
0
0
0
]

=

[
(3/5)×5 + (-4/5)×0
(3/5)×0 + (-4/5)×0
(4/5)×5 + (3/5)×0
(4/5)×0 + (3/5)×0
]
=
[
3
0
4
0
]
= A ✓

UΣV^T =
[
3
0
4
0
]
= A ✓
Final answer:

UΣV^T = A, confirming our SVD decomposition is correct

Applied rules:

• Matrix multiplication: Row by column rule

• Verification: Essential to confirm correctness

• Orthogonality: U^T U = I and V^T V = I

Solution: Exercises 4 to 5
4 Low-Rank Approximation
Exercise 4
Using SVD from Exercise 1, find the best rank-1 approximation of A =
[
3
0
4
0
]
Definition:

Low-Rank Approximation: A_k = U_k Σ_k V_k^T using only first k singular values/vectors

Step 1: Recall SVD from Exercise 1

A = UΣV^T where U =

[
3/5
-4/5
4/5
3/5
]
, Σ =
[
5
0
0
0
]
, V =
[
1
0
0
1
]

Step 2: Form rank-1 approximation A₁

For rank-1 approximation, keep only the first singular value and corresponding vectors:

U₁ =

[
3/5
4/5
]
, σ₁ = 5, V₁^T = [1 0]

Step 3: Compute A₁ = u₁σ₁v₁^T

A₁ = u₁σ₁v₁^T =

[
3/5
4/5
]
× 5 × [1 0]

=

[
3
0
4
0
]

Step 4: Verify this is the best rank-1 approximation

By the Eckart-Young theorem, A₁ minimizes ||A - B||₂ among all rank-1 matrices B

In this case, A₁ = A since A already has rank 1

A₁ =
[
3
0
4
0
]
= A (perfect approximation since A has rank 1)
Final answer:

Best rank-1 approximation is the matrix itself since A has rank 1

Applied rules:

• Eckart-Young theorem: SVD provides optimal low-rank approximations

• Rank determination: Number of non-zero singular values

• Compression: Store only k columns of U, k rows of V, and k singular values

5 Matrix Norms via SVD
Exercise 5
Using SVD from Exercise 2, compute the Frobenius norm and spectral norm of A =
[
1
1
0
1
]
Definition:

Frobenius norm: ||A||_F = √(Σᵢ σᵢ²) (square root of sum of squared singular values)

Spectral norm: ||A||₂ = σ₁ (largest singular value)

Step 1: Recall singular values from Exercise 2

From Exercise 2: σ₁ = √((3 + √5)/2) ≈ 1.618, σ₂ = √((3 - √5)/2) ≈ 0.618

Step 2: Compute Frobenius norm

||A||_F = √(σ₁² + σ₂²) = √((3 + √5)/2 + (3 - √5)/2) = √(3 + √5 + 3 - √5)/2 = √3

Verification: ||A||_F = √(1² + 1² + 0² + 1²) = √3 ✓

Step 3: Compute spectral norm

||A||₂ = σ₁ = √((3 + √5)/2) ≈ 1.618

Step 4: Interpret the results

The spectral norm ||A||₂ = σ₁ represents the maximum "stretching" factor of A

The Frobenius norm ||A||_F = √3 represents the total energy in the matrix

Relationship: ||A||₂ ≤ ||A||_F ≤ √rank(A) × ||A||₂

||A||_F = √3 ≈ 1.732, ||A||₂ = √((3 + √5)/2) ≈ 1.618
Final answer:

Frobenius norm: √3, Spectral norm: √((3 + √5)/2)

Applied rules:

• Norm computation: SVD makes matrix norms trivial to calculate

• Spectral norm: Equals largest singular value

• Frobenius norm: Equals square root of sum of squared singular values

Questions & Answers

Question: Why is SVD so important compared to other matrix decompositions like LU or QR? What makes it special?

Answer: SVD is special for several fundamental reasons:

  • Universal existence: Every matrix has an SVD, unlike other decompositions that require specific conditions (e.g., LU needs invertible leading minors)
  • Geometric insight: SVD reveals the "geometry" of the linear transformation: how much stretching occurs in each direction
  • Optimal low-rank approximations: The Eckart-Young theorem states that truncating SVD gives the best low-rank approximation
  • Robustness: SVD is numerically stable and well-behaved even for nearly singular matrices
  • Physical interpretation: Singular values represent the principal axes of the ellipsoid formed by mapping the unit sphere

In Exercises 4-5, we saw how SVD enables optimal compression and norm computation. This makes SVD invaluable for data science, machine learning, and signal processing.

Question: In Exercise 4, you mentioned low-rank approximation. How is this used in image compression?

Answer: SVD-based image compression works by treating the image as a matrix of pixel values:

  1. Image representation: An m×n grayscale image becomes an m×n matrix A
  2. Low-rank approximation: Compute A_k = U_k Σ_k V_k^T using only the k largest singular values
  3. Storage efficiency: Instead of storing mn values, store only k(m+n+1) values
  4. Reconstruction: A_k approximates the original image with reduced storage requirements

The singular values typically decay rapidly, meaning that keeping only the first few captures most of the image's "energy." In Exercise 4, we saw that even with k=1, we perfectly reconstructed a rank-1 matrix. For natural images, usually k << min(m,n) suffices for good quality.

This principle underlies JPEG compression and many other image processing techniques!

Question: How do I determine the numerical rank of a matrix when working with floating-point arithmetic?

Answer: In floating-point arithmetic, we use a threshold to determine numerical rank:

  1. Compute SVD: Get all singular values σ₁ ≥ σ₂ ≥ ... ≥ σₙ
  2. Set tolerance: Usually ε = machine precision × max(m,n) × σ₁
  3. Count significant values: Count how many σᵢ > ε
  4. Alternative: Use the "elbow method" - plot log(σᵢ) vs i and look for rapid decay

For Exercise 1's matrix, we had σ₁ = 5 and σ₂ = 0 exactly, so rank = 1. In practice, small singular values like 10⁻¹⁶ might appear due to numerical error, and we'd consider them as zero.

MATLAB and NumPy use variations of this approach in their rank() functions. The SVD is essential for robust rank determination!