অধ্যায় 9 — Singular Value Decomposition (SVD)

📖 একটি ছোট গল্প

Netflix-এর recommendation, LSA-এর topic modeling, image compression, এমনকি ChatGPT-র LoRA fine-tuning — সব কিছুর পেছনে একটি গাণিতিক "সুইস আর্মি নাইফ" কাজ করে: SVD (Singular Value Decomposition)।

Eigenvalue শুধু square matrix-এ কাজ করে, কিন্তু SVD যেকোনো matrix-এ কাজ করে। তাই এটি linear algebra-র "সর্বজনীন hammer"।

মূল বিবৃতি

যেকোনো A ∈ ℝ^m×n-কে এভাবে লেখা যায়:

A = U Σ V^T

U ∈ ℝ^m×m — orthogonal (rotation in output space)
Σ ∈ ℝ^m×n — diagonal-এ singular values σ₁ ≥ σ₂ ≥ … ≥ 0
V ∈ ℝ^n×n — orthogonal (rotation in input space)

💡 ইনসাইট

Geometrically: যেকোনো transformation = rotation → scaling → rotation। এটাই SVD-র সবচেয়ে সুন্দর ব্যাখ্যা।

Singular Values-এর অর্থ

σᵢ = matrix কতটুকু "শক্তিশালী" সেই i-তম দিকে। বড় σ = important direction। ছোট σ = noise / অপ্রয়োজনীয় তথ্য।

‖A‖₂ = σ₁ (largest singular value)

rank(A) = nonzero singular value-এর সংখ্যা

Low-Rank Approximation (Eckart–Young)

Top-k singular value রেখে বাকি 0 করলে — Frobenius/L2 অর্থে সেরা rank-k approximation:

A_k = Σ_i=1^k σᵢ uᵢ vᵢ^T

✨ টিপ

এটাই image compression, recommender system, এবং LoRA-র মূল কৌশল। একটি 1000×1000 matrix-কে শুধু top-50 singular value রাখলে ~95% তথ্য বজায় থাকে, কিন্তু storage ১০-২০ গুণ কমে।

SVD vs Eigendecomposition

Eigendecomposition: শুধু square; সবসময় থাকে না; eigenvalue complex হতে পারে।
SVD: যেকোনো shape; সবসময় থাকে; singular value সবসময় real ≥ 0।
সম্পর্ক: A^TA-র eigenvalue = σᵢ²; eigenvector = V-এর column।

Python (NumPy) Implementation

pythonPython · NumPy

import numpy as np

A = np.array([[3.0, 1.0, 1.0],
              [-1.0, 3.0, 1.0]])    # 2x3, not square

U, S, Vt = np.linalg.svd(A, full_matrices=False)
print("U shape:",  U.shape)         # (2, 2)
print("S (singular values):", S)
print("Vt shape:", Vt.shape)        # (2, 3)

# Reconstruction
A_reconstructed = U @ np.diag(S) @ Vt
print("close?", np.allclose(A, A_reconstructed))

# Low-rank approximation: keep top-1
k = 1
A_k = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]
print("rank-1 approx:\n", A_k)

# Image compression demo (grayscale, fake image)
np.random.seed(0)
img = np.random.rand(64, 64)
U, S, Vt = np.linalg.svd(img, full_matrices=False)
for k in [1, 5, 20, 64]:
    approx = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]
    err = np.linalg.norm(img - approx) / np.linalg.norm(img)
    print(f"k={k:3d}  relative error = {err:.4f}")

# Pseudo-inverse via SVD (works even for non-square / singular)
A_pinv = Vt.T @ np.diag(1.0 / S) @ U.T
print("pinv ok?", np.allclose(A_pinv, np.linalg.pinv(img)))

AI/ML সংযোগ

PCA = data matrix-এ SVD; principal direction = V-এর top column।
Latent Semantic Analysis (LSA) = TF-IDF matrix-এর SVD।
Recommender system = user×item rating matrix-এর low-rank SVD।
Image / model compression = top-k singular value রাখা।
LoRA (fine-tuning LLM) = ΔW-কে low-rank দুটি matrix-এ ভাঙা।
Pseudo-inverse = least squares solution-এর numerically stable পদ্ধতি।
Condition number = σ_max / σ_min — numerical stability-র মাপ।

Common Mistakes

full_matrices=True বনাম False — shape ভুল হয়ে যায়।
Singular value-এর order মনে রাখা — সবসময় descending।
Vt ইতিমধ্যেই transpose — আবার transpose করা ভুল।
0 বা প্রায়-0 singular value দিয়ে ভাগ — pseudo-inverse-এ tolerance দিন।

Practice Tasks

3×2 random matrix-এর SVD নিন এবং reconstruct করে error দেখান।
একটি grayscale image (যেকোনো) load করে rank-5, 20, 50 approximation দেখান।
একটি diagonal matrix-এর SVD কেমন হয় বলুন (হাতে)।

Assignment

একটি 100×5 fake "user-rating" matrix বানান (5 user, 100 movie)। SVD নিয়ে rank-2 approximation বের করুন। কোন user কোন user-এর সাথে similar — দেখানোর জন্য U[:, :2]-এ row-গুলো plot করুন।

Interview Questions

SVD ও Eigendecomposition-এর পার্থক্য?
Singular value-এর geometric অর্থ কী?
LoRA কীভাবে low-rank decomposition কাজে লাগায়?
Condition number কী, কেন গুরুত্বপূর্ণ?

Mini Project

"SVD Image Compressor" — একটি grayscale image নিয়ে slider-style k বদলিয়ে compressed version দেখান। x-axis = k, y-axis = reconstruction error — plot করুন। কত k হলে চোখে দেখে পার্থক্য বোঝা যায় না — খুঁজে বের করুন।

Summary · সারসংক্ষেপ

A = UΣV^T — যেকোনো matrix-এর সর্বজনীন decomposition।
Geometric: rotation × scaling × rotation।
Top-k singular value = সেরা rank-k approximation (Eckart–Young)।
PCA, LSA, recommender, LoRA, pseudo-inverse — সব SVD-নির্ভর।

✨ পরবর্তী পদক্ষেপ

Chapter 10-এ আমরা SVD-র সবচেয়ে জনপ্রিয় প্রয়োগ দেখব — PCA, যা high-dimensional data-কে বোঝার মূল হাতিয়ার।

পূর্ববর্তী · CH 8

Linear Transformations

পরবর্তী · CH 10

Principal Component Analysis (PCA)