Singular Value Decomposition (SVD) — full derivation

4.5.40 · Maths › Linear Algebra (Full)

SVD KYA hai?

WHY yeh eigen-decomposition se alag hai? Eigen-decomposition $A = P D P^{- 1}$ sirf square matrices ke liye kaam karta hai, aur orthogonal $P$ tabhi milta hai jab $A$ symmetric ho. SVD har matrix ke liye kaam karta hai, square ho ya na ho, do orthogonal bases ke saath (ek input space $R^{n}$ ke liye, ek output space $R^{m}$ ke liye).

HOW hum isse derive karte hain (first principles se)

Poori derivation ek safe object par tikti hai: $A^{⊤} A$ .

Step 1 — $A^{⊤} A$ symmetric aur positive semi-definite hai

Symmetric: $(A^{⊤} A)^{⊤} = A^{⊤} (A^{⊤})^{⊤} = A^{⊤} A$ . ✓

PSD: kisi bhi $x$ ke liye, $x^{⊤} (A^{⊤} A) x = (A x)^{⊤} (A x) = ∥ A x ∥^{2} \geq 0$ . Toh har eigenvalue $λ_{i} \geq 0$ . Define karo $σ_{i} := λ_{i} \geq 0.$

Step 2 — $A^{⊤} A$ ke eigenvectors se $V$ banao

Spectral Theorem se, orthonormal eigenvectors $v_{1}, \dots, v_{n}$ choose karo: $A^{⊤} A v_{i} = λ_{i} v_{i} = σ_{i}^{2} v_{i}, v_{i}^{⊤} v_{j} = δ_{ij} .$ Inhe is tarah order karo ki $σ_{1} \geq \dots \geq σ_{r} > 0 = σ_{r + 1} = \dots = σ_{n}$ . $V = [v_{1} ∣ \dots ∣ v_{n}]$ set karo. Yeh orthogonal hai: $V^{⊤} V = I_{n}$ . Yahi right singular vectors hain.

Step 3 — $U$ define karo taaki $A v_{i}$ align ho

$i \leq r$ ke liye (jahan $σ_{i} > 0$ ) define karo $u_{i} := \frac{1}{σ _{i}} A v_{i} .$

$σ_{i}$ se divide kyun karte hain? Hum chahte hain ki $u_{i}$ ek unit vector ho. Check karo: $∥ A v_{i} ∥^{2} = (A v_{i})^{⊤} (A v_{i}) = v_{i}^{⊤} A^{⊤} A v_{i} = v_{i}^{⊤} (σ_{i}^{2} v_{i}) = σ_{i}^{2} .$ Toh $∥ A v_{i} ∥ = σ_{i}$ , aur divide karne se $∥ u_{i} ∥ = 1$ ho jata hai. ✓

Kya $u_{i}$ orthonormal hain? $i \neq = j$ ke liye: $u_{i}^{⊤} u_{j} = \frac{1}{σ _{i} σ _{j}} (A v_{i})^{⊤} (A v_{j}) = \frac{1}{σ _{i} σ _{j}} v_{i}^{⊤} A^{⊤} A v_{j} = \frac{σ _{j}^{2}}{σ _{i} σ _{j}} v_{i}^{⊤} v_{j} = \frac{σ _{j}}{σ _{i}} δ_{ij} = 0.$ ✓

Toh ${u_{1}, \dots, u_{r}}$ $R^{m}$ mein ek orthonormal set hai. Isse $u_{1}, \dots, u_{m}$ tak extend karo ek full orthonormal basis banaane ke liye (kisi bhi completion par Gram–Schmidt). $U = [u_{1} ∣ \dots ∣ u_{m}]$ set karo.

Step 4 — Assemble karo aur verify karo ki $A = U Σ V^{⊤}$

Construction se, sabhi $i$ ke liye: $A v_{i} = σ_{i} u_{i} (with σ_{i} = 0 giving A v_{i} = 0 for i > r) .$ Inhe columns ki tarah stack karo: $A [v_{1} \dots v_{n}] = [σ_{1} u_{1} \dots σ_{n} u_{n}]$ , matlab $A V = U Σ.$ Right-multiply karo $V^{⊤}$ se (legal hai kyunki $V V^{⊤} = I_{n}$ ): $A = U Σ V^{⊤} .$

Figure — Singular Value Decomposition (SVD) — full derivation

Chaar fundamental subspaces (free bonus)

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

Maan lo $A = (0 - 1 10)$ (ek $90°$ rotation).

Step A: $A^{⊤} A$ banao. Kyun? Yeh hamara gateway hai. $A^{⊤} A = (01 - 1 0) (0 - 1 10) = (1001) = I .$ Step B: eigenvalues. $λ_{1} = λ_{2} = 1 \Rightarrow σ_{1} = σ_{2} = 1$ . Kyun? Ek pure rotation kuch bhi stretch nahi karta — singular values $= 1$ physically sense banta hai. Step C: koi bhi orthonormal $V$ kaam karega; $V = I$ lo, toh $v_{1} = e_{1}, v_{2} = e_{2}$ . Step D: $u_{i} = \frac{1}{σ _{i}} A v_{i} = A v_{i}$ : $u_{1} = A e_{1} = (0, - 1)^{⊤}$ , $u_{2} = A e_{2} = (1, 0)^{⊤}$ . Toh $U = (0 - 1 10)$ , $Σ = I$ , $V^{⊤} = I$ , aur indeed $U Σ V^{⊤} = A$ . ✓

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

Maan lo $A = 110110$ ( $m = 3, n = 2$ ).

Step A: $A^{⊤} A = (2222)$ . Yeh step kyun? Symmetric $2 \times 2$ , easy eigenproblem. Step B: eigenvalues solve karo $det (A^{⊤} A - λ I) = 0$ : $(2 - λ)^{2} - 4 = 0 \Rightarrow λ (λ - 4) = 0$ . Toh $λ_{1} = 4, λ_{2} = 0$ , aur $σ_{1} = 2, σ_{2} = 0$ milta hai. Rank $r = 1$ . Ek zero kyun? Rows identical hain → rank 1. Step C: $λ_{1} = 4$ ke liye eigenvector: $v_{1} = \frac{1}{2} (1, 1)^{⊤}$ . $λ_{2} = 0$ ke liye: $v_{2} = \frac{1}{2} (1, - 1)^{⊤}$ . Step D: $u_{1} = \frac{1}{σ _{1}} A v_{1} = \frac{1}{2} A \cdot \frac{1}{2} (1, 1)^{⊤} = \frac{1}{2 2} (2, 2, 0)^{⊤} = \frac{1}{2} (1, 1, 0)^{⊤}$ . Kyun? Confirm karta hai ki $∥ u_{1} ∥ = 1$ . Extend karo $u_{2} = \frac{1}{2} (1, - 1, 0)^{⊤}$ , $u_{3} = (0, 0, 1)^{⊤}$ tak basis complete karne ke liye. $A = U 200000 V^{⊤}, U = \frac{1}{2} \frac{1}{2} 0 \frac{1}{2} - \frac{1}{2} 0 001 .$

Common Mistakes (Steel-manned)

Flashcards

SVD derive karne ke liye hum pehle kaunsi object diagonalize karte hain, aur yeh safe kyun hai?

A^{⊤} A

— yeh hamesha symmetric aur positive semi-definite hota hai, toh Spectral Theorem real non-negative eigenvalues ke saath ek orthonormal eigenbasis deta hai.

A^{⊤} A

ke terms mein singular values define karo.

σ_{i} = λ_{i}

jahan

λ_{i} \geq 0

eigenvalues hain

A^{⊤} A

ke.

Left singular vectors

u_{i}

ko kaise define kiya jaata hai (

σ_{i} > 0

ke liye)?

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

, jo guarantee karta hai ki yeh unit vectors hain aur

v_{i}

ke saath correctly paired hain.

Prove karo ki

∥ A v_{i} ∥ = σ_{i}

∥ A v_{i} ∥^{2} = v_{i}^{⊤} A^{⊤} A v_{i} = v_{i}^{⊤} σ_{i}^{2} v_{i} = σ_{i}^{2}

, toh

∥ A v_{i} ∥ = σ_{i}

i \neq = j

ke liye

u_{i}

orthogonal kyun hain?

u_{i}^{⊤} u_{j} = \frac{1}{σ _{i} σ _{j}} v_{i}^{⊤} A^{⊤} A v_{j} = \frac{σ _{j}}{σ _{i}} δ_{ij} = 0

A \in R^{m \times n}

ke liye

U, Σ, V

ke dimensions kya hain?

U

m \times m

hai,

Σ

m \times n

hai,

V

n \times n

hai.

Kaun se singular vectors

A

ke null space ko span karte hain?

Right singular vectors

v_{i}

jinka

σ_{i} = 0

hai (matlab

i > r

A V = U Σ

se final SVD identity kya hai?

A = U Σ V^{⊤}

(

V^{⊤}

se right-multiply karo kyunki

V V^{⊤} = I

Kya SVD sirf square matrices tak restricted hai?

Nahi — yeh har real

m \times n

matrix ke liye exist karta hai, unlike eigen-decomposition.

A = U Σ V^{⊤}

ka geometric matlab kya hai?

Rotate/reflect karo (

V^{⊤}

se), axes ke along stretch karo (

Σ

se), phir se rotate/reflect karo (

U

se).

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ek stamp hai jo paper par ek tedha-medha stretched shape print karta hai. SVD kehta hai ki koi bhi aisa stamp apna kaam teen simple moves mein karta hai: pehle woh paper ko ek saaf angle par spin karta hai, phir usse sirf seedhe upar-neeche aur left-right directions mein stretch karta hai (amounts $σ_{1}, σ_{2}, \dots$ se), phir result ko phir se spin karta hai. Chahe stamp kitna bhi twisted lage, yeh secretly sirf spin–stretch–spin hai. Stretch amounts singular values hain, aur yeh batate hain ki stamp kaunsi directions ki sabse zyada parwah karta hai (bada $σ$ ) aur kaunhe woh zero kar deta hai (zero $σ$ ).

Connections

Spectral Theorem — woh symmetric eigen-decomposition jo Step 1–2 ko power deta hai.
Eigenvalues and Eigenvectors — singular values hain $eigenvalues of A^{⊤} A$ .
Four Fundamental Subspaces — $u_{i}, v_{i}$ charon ke liye orthonormal bases dete hain.
Positive Semi-Definite Matrices — guarantee karta hai ki $λ_{i} \geq 0$ .
Low-Rank Approximation / Principal Component Analysis (PCA) — truncated SVD applications.
Moore-Penrose Pseudoinverse — $A^{+} = V Σ^{+} U^{⊤}$ .
Gram-Schmidt Process — $u_{i}$ ko full basis tak extend karne ke liye use hota hai.