linear-algebraকঠিন⏱ 18 মিনিট

SVD — Singular Value Decomposition

Singular Value Decomposition

🍛

বিরিয়ানির রেসিপি ভাঙা

ধর তোর বন্ধু ফারুক পুরান ঢাকায় বিরিয়ানির দোকান দিছে। তার বিরিয়ানি এতই ফেমাস যে সবাই recipe জানতে চায়। একদিন এক food blogger আসল আর বলল 'মামা, তোমার বিরিয়ানির secret কি?' ফারুক বলল 'ভাই, বিরিয়ানি মানে তিনটা জিনিস — (১) কোন কোন মশলা use করবা (U), (২) কোন মশলা কতটুকু important (Σ — singular values), আর (৩) কোন মশলা কোন স্বাদ দেয় (V^T)।' blogger বলল 'মানে তুমি recipe-টাকে তিন ভাগে decompose করছ?' ফারুক বলল 'এইটাই SVD মামা! যেকোনো জটিল জিনিসরে তিন ভাগে ভাইঙ্গা সোজা করা!'

এইটাই SVD! যেকোনো matrix-কে তিনটা matrix-এর গুণফলে ভাঙা যায়: A = UΣV^T। U হইল left singular vectors (input space-এর directions), Σ হইল singular values (importance/strength), V^T হইল right singular vectors (output space-এর directions)। সবচেয়ে powerful decomposition!

সংজ্ঞা

Singular Value Decomposition (SVD) হইল যেকোনো m×n matrix A-কে তিনটা matrix-এর product-এ ভাঙা: A = UΣV^T। U (m×m) orthogonal matrix, Σ (m×n) diagonal matrix (singular values), V^T (n×n) orthogonal matrix। এইটা square matrix না হইলেও কাজ করে — eigendecomposition-এর generalization!

SVD: যেকোনো Matrix = Rotation × Scaling × Rotation

\[A = U \Sigma V^T\]

ব্যাখ্যা

SVD-এর তিনটা অংশ

A = UΣV^T-তে তিনটা part আছে: V^T প্রথমে input space-এ rotate করে, Σ scale করে (stretch/shrink), তারপর U output space-এ rotate করে। মানে যেকোনো linear transformation = rotation + scaling + rotation! ফারুক মামার ভাষায়: 'প্রথমে মশলা বাছো, তারপর পরিমাণ ঠিক করো, তারপর রান্না করো!'

\[A = U \Sigma V^T, \quad U^TU = I, \quad V^TV = I, \quad \Sigma = \text{diag}(\sigma_1, \sigma_2, \ldots)\]

Singular Values কি বলে

Σ-এর diagonal-এ singular values থাকে: σ₁ ≥ σ₂ ≥ ... ≥ 0। এগুলা বলে কোন direction কতটুকু important। বড় singular value = বেশি important direction। ছোটগুলা noise হইতে পারে — বাদ দিলেও বেশি ক্ষতি নাই। এইটাই low-rank approximation-এর ভিত্তি!

\[\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0, \quad r = \text{rank}(A)\]

Truncated SVD — Low-Rank Approximation

সব singular value না রাইখা top-k টা রাখলে approximate version পাইবা: A ≈ U_k Σ_k V_k^T। Eckart-Young theorem বলে এইটাই best rank-k approximation! Data compression, noise removal, dimensionality reduction — সব এই trick দিয়া হয়।

\[A_k = \sum_{i=1}^{k} \sigma_i \mathbf{u}_i \mathbf{v}_i^T \quad \text{(best rank-k approximation)}\]

Image Compression with SVD

একটা 4×4 grayscale image matrix আছে। SVD দিয়া rank-2 approximation করো আর দেখো কতটুকু information retain হয়।

Step 1: Original Matrix

4×4 image matrix A দেখো

\[A = \begin{bmatrix} 1 & 2 & 1 & 2 \\ 3 & 4 & 3 & 4 \\ 1 & 2 & 1 & 2 \\ 3 & 4 & 3 & 4 \end{bmatrix}\]

Step 2: SVD করো

NumPy দিয়া U, Σ, V^T বাইর করো। দেখবা singular values: σ₁ ≈ 10.0, σ₂ ≈ 1.0, σ₃ ≈ 0, σ₄ ≈ 0। মানে rank = 2!

\[\sigma_1 \approx 10.0, \; \sigma_2 \approx 1.0, \; \sigma_3 = 0, \; \sigma_4 = 0\]

Step 3: Rank-1 Approximation

শুধু σ₁ রাখলে A₁ = σ₁ u₁ v₁^T — একটা rank-1 matrix। Information retained = σ₁²/(σ₁² + σ₂²) ≈ 99%!

\[A_1 = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^T \quad \text{(99% information)}\]

Step 4: Compression Ratio

Original: 4×4 = 16 numbers। Rank-1: 4 + 1 + 4 = 9 numbers। 44% compression with 99% accuracy!

\[\text{Compression} = 1 - \frac{4 + 1 + 4}{16} = 43.75\%\]

উত্তর:

SVD দিয়া rank-2 approximation 100% accurate (কারণ original rank = 2), rank-1 approximation 99% accurate with 44% compression। মামা বলে 'বড় singular value-ই বড় কথা বলে, ছোটগুলা noise!'

ML-এ কোথায় লাগে?

💡

মনে রাখার ট্রিক

SVD = বিরিয়ানি recipe ভাঙা — U (কোন মশলা), Σ (কতটুকু), V^T (কোন স্বাদে)। যেকোনো matrix-কে Rotation × Scaling × Rotation-এ ভাঙো। বড় σ = important, ছোট σ = noise!

#svd#decomposition#singular-values#compression#recommendation#dimensionality-reduction#pseudoinverse

আগের চ্যাপ্টার

eigenvalue eigenvector

পরের চ্যাপ্টার

pca