Singular Value Decomposition (SVD) intuition and computation

1.1.15 · AI-ML › Linear Algebra Essentials

SVD KYA hai?

YE HAMESHA KYO EXIST KARTA HAI (eigendecomposition ke unlike, jise square, diagonalizable matrix chahiye)? Kyunki hum ise $A^{⊤} A$ aur $A A^{⊤}$ se banate hain, jo hamesha symmetric aur positive semidefinite hote hain, isliye unke paas hamesha non-negative eigenvalues ke saath orthonormal eigenvectors ka poora set hota hai.

Ise scratch se KAISE derive karein

Hum chahte hain orthonormal directions jinhein $A$ map kare orthogonal directions mein.

Step 1 — $A^{⊤} A$ dekho. Ye symmetric hai ( $(A^{⊤} A)^{⊤} = A^{⊤} A$ ) aur PSD hai ( $x^{⊤} A^{⊤} A x = ∥ A x ∥^{2} \geq 0$ ). Spectral theorem ke hisaab se iske orthonormal eigenvectors $v_{1}, \dots, v_{n}$ hain aur eigenvalues $λ_{i} \geq 0$ hain: $A^{⊤} A v_{i} = λ_{i} v_{i} .$

Ye step kyun? Symmetric PSD ⇒ guaranteed orthonormal eigenbasis aur non-negative eigenvalues — bilkul wahi raw materials jo humein chahiye.

Step 2 — Singular values define karo. $σ_{i} = λ_{i} \geq 0.$

Kyun? $λ_{i} = ∥ A v_{i} ∥^{2}$ (neeche dekho), isliye $σ_{i} = ∥ A v_{i} ∥$ — ek length hai, isliye non-negative. Yahan "stretch factor" rehta hai.

Check: $∥ A v_{i} ∥^{2} = (A v_{i})^{⊤} (A v_{i}) = v_{i}^{⊤} A^{⊤} A v_{i} = v_{i}^{⊤} λ_{i} v_{i} = λ_{i} .$

Step 3 — Left singular vectors define karo. $σ_{i} > 0$ ke liye set karo $u_{i} = \frac{1}{σ _{i}} A v_{i} .$

Kyun? Ye $A v_{i}$ ko unit length pe normalize karta hai. Aur ye orthonormal nikalta hai: $u_{i}^{⊤} u_{j} = \frac{1}{σ _{i} σ _{j}} v_{i}^{⊤} A^{⊤} A v_{j} = \frac{λ _{j}}{σ _{i} σ _{j}} v_{i}^{⊤} v_{j} = δ_{ij} .$

Step 4 — Dobara jodo. $A v_{i} = σ_{i} u_{i}$ har $i$ ke liye matlab, columns stack karke, $A V = U Σ \Rightarrow A = U Σ V^{⊤}$ ( $V^{- 1} = V^{⊤}$ use karke kyunki $V$ orthogonal hai). ∎

Figure — Singular Value Decomposition (SVD) intuition and computation

Dual coding: unit circle (right singular vectors $v_{i}$ ) → $A$ se map hoke → ek ellipse jiske axes $σ_{i} u_{i}$ hain.

Geometric reading (picture)

$A = U Σ V^{⊤}$ ek vector $x$ par right-to-left kaam karta hai:

$V^{⊤}$ $x$ ko rotate karta hai taaki singular directions ke saath align ho.
$Σ$ axis $i$ ko factor $σ_{i}$ se stretch karta hai (sphere ko ellipsoid bana deta hai).
$U$ result ko output space mein rotate karta hai.

Worked example 1 — ek $2 \times 2$ matrix

Maan lo $A = (30 0 - 2)$ .

Step 1: $A^{⊤} A = (9004)$ . Kyun? Hum hamesha $A^{⊤} A$ se shuru karte hain. Step 2: eigenvalues $9, 4$ ⇒ $σ_{1} = 3, σ_{2} = 2$ , jiske saath $v_{1} = e_{1}, v_{2} = e_{2}$ . Step 3: $u_{1} = \frac{1}{3} A v_{1} = (1, 0)$ , $u_{2} = \frac{1}{2} A v_{2} = (0, - 1)$ . Sign kyun? $A v_{2} = (0, - 2)$ , toh normalize karne se woh flip hota hai — SVD sign ko $U$ mein absorb kar leta hai, $σ > 0$ rakhta hai. Result: $U = (10 0 - 1), Σ = (3002), V = I$ .

Worked example 2 — ek non-square, rank-1 matrix

Maan lo $A = 111111$ ( $3 \times 2$ ).

Step 1: $A^{⊤} A = (3333)$ . Kyun? Column-column dot products. Step 2: $(3333)$ ke eigenvalues $6$ aur $0$ hain ⇒ $σ_{1} = 6, σ_{2} = 0$ . Rank 1 hai! $6$ ke liye eigenvector: $v_{1} = \frac{1}{2} (1, 1)$ . Step 3: $u_{1} = \frac{1}{6} A v_{1} = \frac{1}{6} \cdot \frac{1}{2} (2, 2, 2) = \frac{1}{3} (1, 1, 1)$ . Kyun? $A v_{1} = \frac{1}{2} (2, 2, 2)$ ; $σ_{1} = 6$ se divide karne par unit vector milta hai. Result: $A = 6 u_{1} v_{1}^{⊤}$ — ek single rank-1 term, jaisa expected tha.

80/20: SVD kis kaam aata hai

Common mistakes (steel-manned)

Active recall

Recall Feynman: ek 12-saal ke bacche ko samjhao

Socho ek stamp jo atta ka gol loa dabaa ke oval pancake bana deta hai. SVD kehta hai stamp ek ke baad ek teen saaf kaam karta hai: loe ko spin karo, use ek taraf doosre se zyada stretch karo, phir dobara spin karo. Stretch ki matra (oval ki baahein kitni lambi hain) singular values hain. Agar ek stretch bahut chhota hai, tum pretend kar sakte ho ke woh zero hai aur phir bhi almost wahi pancake milega — isi tarah computers photos ko compress karte hain.

Flashcards

A = U Σ V^{⊤}

mein teen geometric actions kya hain?

Rotate karo (

V^{⊤}

), axes ke saath stretch karo (

Σ

), dobara rotate karo (

U

A

ke singular values kaise compute karte hain?

A^{⊤} A

ke eigenvalues ke square roots lo (equivalently

A A^{⊤}

ke bhi).

Singular values hamesha non-negative kyun hote hain?

∥ A v_{i} ∥ = λ_{i} (A^{⊤} A)

ke barabar hain, jo ek length hai, isliye

\geq 0

; signs

U, V

mein absorb ho jaate hain.

Right singular vectors

v_{i}

kahan se aate hain?

A^{⊤} A

ke orthonormal eigenvectors se.

v_{i}

aur

σ_{i} > 0

diye hue,

u_{i}

kaise nikaalte hain?

u_{i} = \frac{1}{σ _{i}} A v_{i}

SVD har matrix ke liye exist kyun karta hai lekin eigendecomposition nahi karta?

A^{⊤} A

hamesha symmetric PSD hota hai, isliye spectral theorem hamesha apply hota hai.

A

ka best rank-

k

approximation batao.

A_{k} = \sum_{i = 1}^{k} σ_{i} u_{i} v_{i}^{⊤}

(Eckart–Young); error

= σ_{k + 1}

SVD ka PCA se kya relation hai?

Centered

X = U Σ V^{⊤}

ke liye,

V

ke columns principal directions hain aur

σ_{i}^{2} / (m - 1)

variances hain.

σ_{1}

geometrically kya hai?

Image ellipsoid ki sabse lambi semi-axis =

max_{∥ x ∥ = 1} ∥ A x ∥

= operator (spectral) norm.

SVD eigendecomposition ke saath kab coincide karta hai?

Jab

A

symmetric positive semidefinite ho.

Connections

Eigenvalues and Eigenvectors — SVD $A^{⊤} A$ ke eigenpairs se bana hai.
Spectral Theorem — woh orthonormal eigenbasis guarantee karta hai jis par SVD rely karta hai.
Principal Component Analysis (PCA) — $V$ aur $σ_{i}^{2}$ ka direct application.
Orthogonal Matrices — kyun $U, V$ length preserve karte hain (pure rotations/reflections).
Matrix Norms — $∥ A ∥_{2} = σ_{1}$ , $∥ A ∥_{F} = \sum σ_{i}^{2}$ .
Pseudoinverse (Moore–Penrose) — $A^{+} = V Σ^{+} U^{⊤}$ .
Rank of a Matrix — rank = nonzero singular values ki sankhya.