Singular Value Decomposition (SVD) — full derivation: Worked examples

4.5.40 · D3 · Maths › Linear Algebra (Full) › Singular Value Decomposition (SVD) — full derivation

Neeche sab kuch parent recipe pe lean karta hai: the four-step SVD recipe. Jab hum "form $A^{⊤} A$ " kehte hain toh humara matlab hai Positive Semi-Definite Matrices ka gateway, jiska eigenbasis Spectral Theorem se aata hai.

Scenario matrix

Har matrix jo tumhe di ja sakti hai in case classes mein se ek mein aati hai. Last column batata hai kaunsa worked example us cell ko cover karta hai.

#	Case class	Kya cheez tricky banati hai	Covered by
C1	Square, full-rank, symmetric	Kya $σ_{i}$ eigenvalues ke barabar hote hain? Signs!	Example 1
C2	Square, negative eigenvalue	$λ (A) < 0$ lekin $σ \geq 0$	Example 2
C3	Square, complex eigenvalues (rotation-like)	$A$ ke koi real eigenvectors nahi hain	Example 3
C4	Diagonal with mixed signs	Kya $Σ$ sirf $	A
C5	Tall, rank-deficient ( $m > n$ , $r < n$ )	Zero $σ$ , null space, extend $U$	Example 5
C6	Wide, full row rank ( $m < n$ , $r = m$ )	Null space $v$ 's mein rehta hai	Example 6
C7	Wide, rank-deficient ( $m < n$ , $r < m$ )	Zeros DONO $u$ 's aur $v$ 's mein	Example 7
C8	Zero / degenerate matrix	$σ_{1} = 0$ , limiting case	Example 8
C9	Word problem (data / stretching)	$σ_{i}$ se geometry padho	Example 9

Notation reminder, taaki koi symbol unearned na rahe:

$A^{⊤}$ = transpose: $A$ ko uske diagonal ke across flip karo (rows columns ban jaati hain).
$∥ x ∥$ = vector $x$ ki length, $x_{1}^{2} + x_{2}^{2} + \dots$ .
$δ_{ij} = 1$ agar $i = j$ , warna $0$ (the "kya ye same index hain?" switch).
$det$ = determinant; $det (M - λ I) = 0$ solve karne se $M$ ke eigenvalues $λ$ milte hain (dekho Eigenvalues and Eigenvectors).
$r$ = rank = nonzero singular values ki sankhya = woh truly independent directions jinhe $A$ rakhta hai.
$e_{i}$ aur $Σ$ : upar callout mein define hain.

Example 1 — C1: symmetric, full-rank square

Forecast: singular values padhne se pehle guess karo. Diagonal, positive... kya $Σ$ sirf $A$ copy kar leta hai?

$A^{⊤} A$ form karo. $A^{⊤} A = (2003) (2003) = (4009) .$ Ye step kyun? Parent recipe ka safe symmetric gateway hai.
Eigenvalues. Already diagonal: $λ_{1} = 9, λ_{2} = 4$ . So $σ_{1} = 9 = 3, σ_{2} = 4 = 2$ . Ye step kyun? $σ_{i} = λ_{i}$ ; biggest-first order karne ka matlab hai $σ_{1} = 3$ .
$V$ banao. $λ = 9$ ka eigenvector $e_{2} = (0, 1)^{⊤}$ hai; $λ = 4$ ka $e_{1} = (1, 0)^{⊤}$ . So $V = (0110)$ . Ye step kyun? Humein $v_{i}$ ko $σ_{i}$ ke same order mein list karna hai.
$u_{i} = \frac{1}{σ _{i}} A v_{i}$ define karo. $u_{1} = \frac{1}{3} A (0, 1)^{⊤} = \frac{1}{3} (0, 3)^{⊤} = (0, 1)^{⊤}$ ; $u_{2} = \frac{1}{2} A (1, 0)^{⊤} = \frac{1}{2} (2, 0)^{⊤} = (1, 0)^{⊤}$ . So $U = (0110)$ . Ye step kyun? $v_{i}$ se $u_{i}$ define karna sahi sign lock karta hai (parent ke "sign trap" se bachata hai).

Verify: $U Σ V^{⊤} = (0110) (3002) (0110) = (2003) = A .$ ✓ Note karo $σ$ 's ko $A$ ki entries se reorder kiya gaya — copy karna automatic nahi hai.

Example 2 — C2: ek negative eigenvalue

Forecast: $A$ ka eigenvalue $- 3$ hai. Kya koi singular value $- 3$ hoga?

$A^{⊤} A$ form karo. $(- 3 0 01) (- 3 0 01) = (9001)$ . Ye step kyun? Square karne se sign khatam ho jaata hai — yahi to poora point hai.
$A^{⊤} A$ ke eigenvalues: $9, 1$ . So $σ_{1} = 3, σ_{2} = 1$ . Ye step kyun? $σ_{i} = λ_{i} (A^{⊤} A) \geq 0$ hamesha, unlike $λ (A)$ .

Verify: $σ_{1} = 3 = ∣ - 3∣$ , na ki $- 3$ . Reflection (negative eigenvalue) $U$ ke andar store hota hai, $Σ$ mein nahi. Sanity: $∥ A e_{1} ∥ = ∥ (- 3, 0)^{⊤} ∥ = 3 = σ_{1}$ . ✓ Ye parent ke mistake box ka direct jawab hai: singular values kabhi $A$ ke eigenvalues nahi hote.

Example 3 — C3: complex eigenvalues (ek rotation)

Forecast: ek rotation har vector ko bina uski length badlaye ghuma deta hai. $σ_{i}$ kya hone chahiye?

Figure — Singular Value Decomposition (SVD) — full derivation

Figure s01 (Example 3). Left: inputs ka blue unit circle. Right: $A$ apply karne ke baad wahi circle (red) — abhi bhi unit circle hai, aur yellow arrow ek input ko same length pe land karte dikhata hai. Ise step 3 mein use karo: koi bhi direction stretch nahi hota, isliye har $σ_{i} = 1$ .

Trap yaad karo. $A$ ke eigenvalues $e^{\pm i 3 0^{\circ}}$ hain — complex, isliye $A$ ke koi real eigenvectors nahi hain. $R$ ke upar Eigen-decomposition fail ho jaati hai. SVD ko koi farak nahi padta. Ye step kyun? Ye motivate karta hai ki kyun $A^{⊤} A$ (real, symmetric) humein bachata hai.
$A^{⊤} A$ form karo. Koi bhi rotation $R$ ye satisfy karta hai: $R^{⊤} R = I$ , isliye $A^{⊤} A = I = (1001)$ . Ye step kyun? Rotation ke columns orthonormal hote hain, identity dete hain.
$I$ ke eigenvalues: characteristic polynomial $(1 - λ)^{2} = 0$ hai, ek repeated root $λ = 1$ (multiplicity two). So $σ_{1} = σ_{2} = 1 = 1$ . Ye step kyun? $1 = 1$ : ek rotation kuch bhi stretch nahi karta — figure s01 se match.
$V, U$ banao. $A^{⊤} A = I$ ke saath, koi bhi orthonormal $V$ kaam karega — $V = I$ lo. Phir $u_{i} = A v_{i}$ , isliye $U = A$ . Ye step kyun? $Σ = I$ hai, isliye $A = U \cdot I \cdot I^{⊤} = A$ trivially. Puri matrix rotation $U$ mein chhup jaati hai.

Verify: $A^{⊤} A = I$ aur dono singular values $1$ ke barabar hain (characteristic polynomial $(1 - λ)^{2}$ ka ek hi distinct root $1$ hai). Geometrically, figure s01 mein red circle kabhi bada nahi hua. ✓

Example 4 — C4: mixed signs ke saath diagonal

Forecast: kaunsi entry $σ_{1}$ ban jaayegi?

$A^{⊤} A$ form karo. Diagonal squared: $diag (16, 0, 4)$ . Ye step kyun? Gateway; diagonals entrywise square hote hain.
Eigenvalues $16, 4, 0 \Rightarrow σ = 4, 2, 0$ . Rank $r = 2$ . Ye step kyun? Biggest-first order karo: $σ_{1} = 4, σ_{2} = 2, σ_{3} = 0$ .
$V$ : columns standard basis ko reorder karke match karo — $v_{1} = e_{1}, v_{2} = e_{3}, v_{3} = e_{2}$ . Ye step kyun? $V$ ke columns $σ_{i}$ ke same order mein appear hone chahiye — $e_{1}$ carries $λ = 16$ , $e_{3}$ carries $λ = 4$ , aur $e_{2}$ carries $λ = 0$ , isliye ye $σ_{1}, σ_{2}, σ_{3}$ ke saath line up hote hain.
$U$ : $u_{1} = \frac{1}{4} A e_{1} = \frac{1}{4} (- 4, 0, 0)^{⊤} = (- 1, 0, 0)^{⊤}$ ; $u_{2} = \frac{1}{2} A e_{3} = (0, 0, 1)^{⊤}$ ; $u_{3} = (0, 1, 0)^{⊤}$ se complete karo. Ye step kyun? $u_{1}$ mein sign $- 1$ $A$ ki negative entry absorb karta hai.

Verify: singular values hain ${4, 2, 0} = {∣ - 4∣, ∣2∣, ∣0∣}$ sorted — absolute values, phir descending. ✓

Example 5 — C5: tall, rank-deficient

Forecast: doosra column pehle ka exactly do guna hai... kitne nonzero $σ$ honge?

$A^{⊤} A$ form karo. $(122424) 122244 = (9181836)$ . Ye step kyun? $A$ $3 \times 2$ hai (square nahi), isliye iske apne eigenvalues nahi hain; $A^{⊤} A$ ek $2 \times 2$ symmetric gateway hai jise hum diagonalize kar sakte hain.
Eigenvalues: $det (9 - λ 18 18 36 - λ) = λ^{2} - 45 λ = 0 \Rightarrow λ = 45, 0$ . So $σ_{1} = 45 = 35, σ_{2} = 0$ . Rank $r = 1$ . Ye step kyun? Ek zero eigenvalue dependent columns confirm karta hai.
$V$ : $λ = 45$ ke liye: $(9 - 45) x + 18 y = 0 \Rightarrow x = y /2$ , isliye $v_{1} = \frac{1}{5} (1, 2)^{⊤}$ . $λ = 0$ ke liye: $v_{2} = \frac{1}{5} (2, - 1)^{⊤}$ . Ye step kyun? $v_{2}$ (with $σ_{2} = 0$ ) null space span karta hai: $A v_{2} = 0$ .
$U$ : $u_{1} = \frac{1}{3 5} A v_{1} = \frac{1}{3 5} \cdot \frac{1}{5} (5, 10, 10)^{⊤} = \frac{1}{3} (1, 2, 2)^{⊤}$ . Phir Gram–Schmidt se $u_{2}, u_{3} ⊥ u_{1}$ tak extend karo; jaise $u_{2} = \frac{1}{5} (2, - 1, 0)^{⊤}$ , $u_{3} = \frac{1}{45} (2, 4, - 5)^{⊤}$ . Ye step kyun? $u_{2}, u_{3}$ left null space span karte hain — wo directions jinhe $A$ kabhi reach nahi karta.

Verify: $∥ A v_{1} ∥ = ∥ \frac{1}{5} (5, 10, 10)^{⊤} ∥ = \frac{1}{5} 225 = \frac{15}{5} = 35 = σ_{1}$ . ✓ Aur $A v_{2} = \frac{1}{5} A (2, - 1)^{⊤} = \frac{1}{5} (0, 0, 0)^{⊤} = 0$ . ✓

Example 6 — C6: wide, full row rank

Forecast: output ( $m = 2$ ) se zyada input directions ( $n = 3$ ) hain. Extra dimension kahan jaati hai?

$A^{⊤} A$ form karo ( $3 \times 3$ ): $9000000016$ . Ye step kyun? $A^{⊤} A$ hamesha $n \times n$ hota hai; yahan wo $3 \times 3$ hai.
Eigenvalues $16, 9, 0 \Rightarrow σ_{1} = 4, σ_{2} = 3, σ_{3} = 0$ . Rank $r = 2$ . Ye step kyun? $σ_{i} = λ_{i}$ , biggest-first order karo; ek zero eigenvalue batata hai ki ek input direction kill ho jaati hai, chahe dono rows independent hon.
$V$ : $v_{1} = e_{3}, v_{2} = e_{1}, v_{3} = e_{2}$ ( $e_{2}$ direction ka $σ = 0$ hai). Ye step kyun? $v_{3} = e_{2}$ null direction hai: $A e_{2} = (0, 0)^{⊤}$ .
$U$ ( $2 \times 2$ ): $u_{1} = \frac{1}{4} A e_{3} = (0, 1)^{⊤}$ ; $u_{2} = \frac{1}{3} A e_{1} = (1, 0)^{⊤}$ . $U = (0110)$ . Ye step kyun? Sirf $r = 2$ left singular vectors chahiye aur $m = 2$ hai, isliye $U$ already complete hai.
$Σ$ $2 \times 3$ hai: $(400300)$ . Ye step kyun? $Σ$ $A$ ka shape leta hai — parent ka teesra mistake box.

Verify: $U Σ V^{⊤}$ : $V^{⊤}$ mein rows $v_{1}^{⊤}, v_{2}^{⊤}, v_{3}^{⊤}$ hain. Reconstruction $(300004)$ wapas deta hai. Check karo $σ_{1}^{2} + σ_{2}^{2} = 16 + 9 = 25 = 3^{2} + 4^{2} =$ $A$ ki squared entries ka sum (Frobenius). ✓

Example 7 — C7: wide AUR rank-deficient

Forecast: wide aur rows dependent hain. Kitne nonzero $σ$ honge, aur total mein kitni zero directions hongi?

$A^{⊤} A$ form karo ( $3 \times 3$ ): $110220 (121200) = 550550000$ . Ye step kyun? Safe $n \times n$ gateway; ye do zero eigenvalues expose karega (ek wide shape se, ek dependent rows se).
Eigenvalues: top-left $2 \times 2$ block $(5555)$ deta hai $λ^{2} - 10 λ = 0 \Rightarrow λ = 10, 0$ ; teesri row/column ek aur $λ = 0$ contribute karta hai. So $λ = 10, 0, 0 \Rightarrow σ_{1} = 10, σ_{2} = σ_{3} = 0$ . Rank $r = 1$ . Ye step kyun? Sirf ek nonzero singular value bachta hai — matrix truly ek hi direction rakhti hai.
$V$ : $λ = 10$ ke liye: $(5 - 10) x + 5 y = 0 \Rightarrow y = x$ , isliye $v_{1} = \frac{1}{2} (1, 1, 0)^{⊤}$ . Null space ( $σ = 0$ span karta hai) hai $v_{2} = \frac{1}{2} (1, - 1, 0)^{⊤}, v_{3} = (0, 0, 1)^{⊤}$ . Ye step kyun? $v_{2}, v_{3}$ dono $A v_{i} = 0$ satisfy karte hain — ek wide rank-deficient matrix ka pura $2$ -dimensional null space.
$U$ ( $2 \times 2$ ): $u_{1} = \frac{1}{10} A v_{1} = \frac{1}{10} \cdot \frac{1}{2} (2, 4)^{⊤} = \frac{1}{5} (1, 2)^{⊤}$ . $u_{2} = \frac{1}{5} (2, - 1)^{⊤}$ se complete karo. Ye step kyun? $u_{2}$ left null space span karta hai; $A$ us output direction ko kabhi reach nahi karta.

Verify: $∥ A v_{1} ∥ = \frac{1}{2} ∥ (2, 4)^{⊤} ∥ = \frac{1}{2} 20 = 10 = σ_{1}$ . ✓ Dono $A v_{2} = \frac{1}{2} A (1, - 1, 0)^{⊤} = (0, 0)^{⊤}$ aur $A v_{3} = A (0, 0, 1)^{⊤} = (0, 0)^{⊤}$ . ✓ Do zero directions double $σ = 0$ confirm karte hain.

Example 8 — C8: zero / degenerate matrix

Forecast: ek matrix jo sab kuch origin pe bhej deti hai. $σ_{1}$ kya hoga?

$A^{⊤} A$ form karo $= (0000)$ . Ye step kyun? Ek fully degenerate matrix bhi usi gateway se guzarti hai; $A^{⊤} A$ abhi bhi symmetric hai aur iske eigenvalues abhi bhi $σ_{i}$ dete hain.
Eigenvalues dono $0 \Rightarrow σ_{1} = σ_{2} = 0$ . Rank $r = 0$ . Ye step kyun? Kisi bhi direction mein koi stretching nahi — total collapse.
$V, U$ : $Σ = 0$ hai, isliye koi bhi orthonormal $U, V$ kaam karega; $U = V = I$ lo. Ye step kyun? $σ_{i} = 0$ ke saath hum kabhi $u_{i} = A v_{i} / σ_{i}$ use nahi kar sakte ( $0$ se division), isliye hum freely ek orthonormal completion choose karte hain — parent ka Gram–Schmidt extension extreme case mein.

Verify: $U Σ V^{⊤} = I \cdot 0 \cdot I = 0 = A$ . ✓ Ye har $σ_{i} \to 0$ shrink karne ki limit hai: geometry ek point pe degenerate ho jaati hai.

Example 9 — C9: ek word problem (stretching data)

Forecast: unit $x$ pe $∥ A x ∥$ ka sabse bada possible value exactly $σ_{1}$ hai — guess karo.

Figure s02 (Example 9). Left: possible unit inputs ka blue unit circle, best direction $v_{1}$ (yellow) aur erased direction $v_{2}$ (red) ke saath. Right: $A$ ke baad, circle $x$ -axis par half-length $5$ ke red flat segment mein collapse ho jaata hai; yellow arrow $A v_{1} = (5, 0)$ maximal stretch hai, aur $v_{2}$ origin pe land karta hai. Part (a) yellow arrow ki length se aur part (b) red arrow se padho.

Model. Max amplification $= max_{∥ x ∥ = 1} ∥ A x ∥ = σ_{1}$ ; erase hoti directions ka $σ = 0$ hota hai. Ye step kyun? Ye singular values ka operational meaning hai.
$A^{⊤} A$ form karo $= (4300) (4030) = (1612129)$ . Ye step kyun? Gateway phir: iske top eigenvalue ka square root precisely wahi maximal amplification factor hai jo poocha gaya, aur iska zero eigenvalue erased direction flag karta hai.
Eigenvalues: $λ^{2} - 25 λ = 0 \Rightarrow λ = 25, 0$ . So $σ_{1} = 5, σ_{2} = 0$ . Ye step kyun? $σ_{1} = 5$ (a) ka jawab hai; $σ_{2} = 0$ ek erased direction flag karta hai.
Right vectors: $λ = 25$ : $(16 - 25) x + 12 y = 0 \Rightarrow y = \frac{3}{4} x$ , $v_{1} = \frac{1}{5} (4, 3)^{⊤}$ . $λ = 0$ : $v_{2} = \frac{1}{5} (3, - 4)^{⊤}$ . Ye step kyun? $v_{2}$ woh input direction hai jiska $σ = 0$ hai: (b) ka jawab.

Verify (a): best input $v_{1}$ dalo: $A v_{1} = \frac{1}{5} A (4, 3)^{⊤} = \frac{1}{5} (25, 0)^{⊤} = (5, 0)^{⊤}$ , length $5 = σ_{1}$ . ✓ Verify (b): $A v_{2} = \frac{1}{5} A (3, - 4)^{⊤} = \frac{1}{5} (0, 0)^{⊤} = 0$ — direction $(3, - 4)$ (yaani $(4, 3)$ ke $⊥$ ) erase ho jaati hai. ✓ Figure s02 dekho: blue unit circle $x$ -axis par half-length $5$ ke red flat segment ban jaata hai; perpendicular blue arrow origin pe land karta hai.

Recall Har example ne kaunsa cell solve kiya?

C1→Ex1, C2→Ex2, C3→Ex3, C4→Ex4, C5→Ex5, C6→Ex6, C7→Ex7, C8→Ex8, C9→Ex9. ::: Scenario matrix ki har row cover ho gayi, including wide-full-rank aur wide-rank-deficient dono.

Ye related pages iske baad revisit karne layak hain: Low-Rank Approximation (sirf top $σ_{i}$ rakho), Principal Component Analysis (PCA) (centred data ka SVD), aur Moore-Penrose Pseudoinverse (nonzero $σ$ par $1/ σ_{i}$ se invert karo).