Singular Value Decomposition (SVD) — full derivation: Visual walkthrough

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

Hum sab kuch ground up se banate hain. Agar aapne kabhi matrix ko space par "act" karte nahi dekha, Step 0 se shuru karo aur skip mat karo.

Step 0 — "Ek matrix space par act karti hai" ka matlab kya hai?

KYA. Ek matrix $A$ ek machine hai. Aap isme ek arrow (vector $x$ ) daalte ho, woh doosra arrow $A x$ nikaalti hai. Ek saath har arrow daalne par hum dekh sakte hain ki woh poori shape ka kya karta hai.

YE YAHAN SE SHURU KYON. SVD ka har claim is machine ke shape-changing behaviour ke baare mein hai. Koi bhi symbol aane se pehle hume input shape aur output shape picture karna aana chahiye.

PICTURE. Unit circle lo — saari length $1$ wali arrows, har direction mein point karti hui. Dekho $A$ iske saath kya karta hai.

Figure — Singular Value Decomposition (SVD) — full derivation

Poori derivation jis bade sawaal ka jawaab deti hai:

Step 1 — Woh do frames jo hum dhundh rahe hain

KYA. Hume do special sets of perpendicular arrows chahiye:

$v_{1}, v_{2}$ input circle mein — woh arrows jo ellipse ke axes par exactly utarenge.
$u_{1}, u_{2}$ output mein — unit arrows un axes ki direction mein point karte hue.
$σ_{1}, σ_{2}$ — har axis kitni lambi hai (stretch amounts).

KYO. Agar hum yeh dhundh lein, toh machine completely ek sentence se describe ho jaati hai: " $A$ , $v_{i}$ ko ek $σ_{i}$ -guna lamba arrow direction $u_{i}$ mein bhejta hai." Baaki sab bookkeeping hai.

PICTURE. Wohi circle-to-ellipse, ab special arrows draw karke.

Target relationship, term by term: $machine A special input v_{i} = stretch σ_{i} output direction u_{i}$

Zor se padho: " $A$ ka $v_{i}$ par act karna $σ_{i}$ times $u_{i}$ ke barabar hai." Page ke baaki hisse ke liye hamaara kaam: sabit karo ki aise $v_{i}, u_{i}, σ_{i}$ hamesha exist karte hain aur unhe dhundho.

Step 2 — $A$ ko directly attack nahi kar sakte, isliye $A^{⊤} A$ banate hain

KYA. $A$ rectangular ho sakta hai, tilted ho sakta hai, perpendicular eigen-arrows ke bina — pakadna mushkil. Toh hum ek friendlier matrix banate hain: $A^{⊤} A$ . Yahan $A^{⊤}$ (padho " $A$ transpose") $A$ ko uske diagonal ke across flip karna hai.

YEH TOOL KYO AUR KOI NAHI. Hume ek aisi matrix chahiye jiske paas guaranteed perpendicular special directions hon. Ek matrix ke paas perpendicular eigen-arrows ka full set hota hai exactly jab woh symmetric hoti hai (woh Spectral Theorem hai). Aur $A^{⊤} A$ hamesha symmetric hoti hai — proof picture mein. Yahi poora reason hai ki hum iske through detour lete hain.

PICTURE. $A^{⊤} A$ symmetric kyon hai? Ise flip karne se kuch nahi badalata.

$(A^{⊤} A)^{⊤} = A^{⊤} (A^{⊤})^{⊤} = A^{⊤} A$

Term by term: $(X Y)^{⊤} = Y^{⊤} X^{⊤}$ order flip karta hai; $(A^{⊤})^{⊤} = A$ ek flip ko undo karta hai. Result wohi nikaalta hai jisse shuru kiya — yahi symmetric ki definition hai.

Step 3 — $A^{⊤} A$ ke eigen-arrows hamare $v_{i}$ ban jaate hain

KYA. $A^{⊤} A$ ke liye eigen-problem solve karo: perpendicular unit arrows $v_{i}$ aur numbers $λ_{i}$ dhundho jaise ki $A^{⊤} A v_{i} = λ_{i} v_{i}, v_{i}^{⊤} v_{j} = δ_{ij} .$ Phir define karo $σ_{i} := λ_{i}$ .

KYO. Ek eigenvector $v_{i}$ ek aisa arrow hai jise matrix rotate nahi karta — sirf $λ_{i}$ se scale karta hai (dekho Eigenvalues and Eigenvectors). Yeh un-rotated, mutually perpendicular arrows exactly woh special input directions hain jo Step 1 mein dhundhe the. Symbol $δ_{ij}$ (Kronecker delta) sirf shorthand hai: $1$ jab $i = j$ , $0$ otherwise — yeh kehta hai "perpendicular unit arrows".

PICTURE. $A^{⊤} A$ har $v_{i}$ ko same direction mein rakhta hai, sirf scale karta hai.

Arrows ko order karo taaki $σ_{1} \geq σ_{2} \geq \dots \geq σ_{r} > 0 = σ_{r + 1} = \dots$ . Yahan $r$ rank hai: non-zero stretches ki count. Arrows ko side by side stack karne se matrix $V = [v_{1} ∣ \dots ∣ v_{n}]$ milti hai, jo orthogonal hai ( $V^{⊤} V = I$ ) kyunki iske columns perpendicular unit arrows hain.

Step 4 — Har $v_{i}$ ko $A$ ke through push karke $u_{i}$ paao

KYA. Har $i$ ke liye jahan $σ_{i} > 0$ , define karo $u_{i} := \frac{1}{σ _{i}} A v_{i} .$

$σ_{i}$ se divide kyon? $A v_{i}$ sahi direction mein point karta hai (ellipse axis ke along) lekin galat length hai. Yeh kitna lamba hai? Compute karo: $∥ A v_{i} ∥^{2} = (A v_{i})^{⊤} (A v_{i}) = v_{i}^{⊤} = σ_{i}^{2} v_{i} A^{⊤} A v_{i} = σ_{i}^{2} v_{i}^{⊤} v_{i} = σ_{i}^{2} .$ Term by term: arrows regroup karo; Step 3 ki eigen-equation substitute karo; $v_{i}^{⊤} v_{i} = 1$ use karo. Toh $∥ A v_{i} ∥ = σ_{i}$ . $σ_{i}$ se divide karne par yeh length $1$ par rescale ho jaata hai — ab yeh ek legit unit direction $u_{i}$ hai. Yahan $λ_{i}$ bhi kaam aata hai: $∥ A v_{i} ∥ = σ_{i} = λ_{i}$ , ek clean stretch.

PICTURE. Dekho $v_{i}$ $A v_{i}$ (length $σ_{i}$ ) par jaata hai, phir unit arrow $u_{i}$ tak shrink hota hai.

Kya $u_{i}$ ek doosre ke perpendicular hain? Haan — $i \neq = j$ ke liye check karo: $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} = 0.$ Aakhri equality isliye hold karti hai kyunki $v_{i}^{⊤} v_{j} = 0$ (Step 3 ki perpendicularity). Toh $u_{1}, \dots, u_{r}$ perpendicular unit arrows hain.

Step 5 — Output basis complete karo (bache hue directions)

KYA. Hamare paas $u_{1}, \dots, u_{r}$ hain (har non-zero $σ_{i}$ ke liye ek). Agar output space $R^{m}$ , $r$ se bada hai, toh bhi hume $u_{r + 1}, \dots, u_{m}$ chahiye ise fill karne ke liye. Hum unhe Gram-Schmidt Process se invent karte hain: gaps fill karne ke liye koi bhi arrows choose karo, phir unhe perpendicular unit arrows mein straighten karo.

KYO. $U$ ek poori $m \times m$ orthogonal matrix (ek complete frame) honi chahiye, chahe $A$ sirf output ke ek $r$ -dimensional slice tak pahunche. Extra $u$ 's un directions mein point karte hain jahan $A$ kabhi nahi pahunchta — left null space.

PICTURE. Do reached axes $u_{1}, u_{2}$ plus ek unreached direction $u_{3}$ jo 3D space complete karta hai.

Sab ko stack karne par $U = [u_{1} ∣ \dots ∣ u_{m}]$ milta hai, construction se orthogonal. Step 3 ke $V$ ke saath, yeh Four Fundamental Subspaces ke char bases hain.

Step 6 — $A = U Σ V^{⊤}$ assemble karo

KYA. Single fact $A v_{i} = σ_{i} u_{i}$ (har $i$ ke liye sach: jab $σ_{i} = 0$ toh dono sides zero arrow hain) ko ek matrix equation mein collect karo.

KYO. Har column ke saath same cheez karna hi matrix multiplication hai. $A v_{i} = σ_{i} u_{i}$ ko columns mein stack karna: $A [v_{1} \dots v_{n}] = [σ_{1} u_{1} \dots σ_{n} u_{n}] ⟹ A V = U Σ.$ Yahan $Σ$ ek $m \times n$ box hai jisme $σ_{i}$ uske diagonal par hain ( $A$ jaisi shape — yeh generally square nahi hoti), taaki $U Σ$ , $u_{i}$ ke aage $σ_{i}$ place kare.

Dono sides ko $V^{⊤}$ se right-multiply karo. Kyunki $V$ orthogonal hai, $V V^{⊤} = I$ (rotate karke un-rotate karna kuch nahi badalata): $A V V^{⊤} = U Σ V^{⊤} ⟹ A = U Σ V^{⊤} .$

PICTURE. Famous three-move factory: input frame → turn ( $V^{⊤}$ ) → stretch ( $Σ$ ) → turn ( $U$ ) → output.

Moves right to left padho (woh order jisme woh ek input $x$ ko $U Σ V^{⊤} x$ mein hit karte hain):

$V^{⊤}$ : input ko rotate karo taaki special arrows $v_{i}$ coordinate axes ke saath align karein.
$Σ$ : axis $i$ ko $σ_{i}$ se stretch karo (aur kisi bhi axis ko $0$ par squash karo jiske liye $σ_{i} = 0$ ).
$U$ : stretched result ko uske final resting frame mein rotate karo.

Step 7 — Degenerate cases (kuch bhi chance par nahi chhoda)

KYA AUR KYO. SVD claim karta hai ki har matrix ke liye kaam karta hai. Toh hume ugly inputs se bachna hai. Har ek ka ek panel neeche hai.

Ek-picture summary

Is page ki poori cheez ek hi diagram mein: perpendicular input frame $v_{i}$ → har ek $σ_{i}$ se stretch → perpendicular output frame $u_{i}$ par utarta hai, ellipse trace karta hua. Do frames plus stretch numbers hi SVD hain.

Recall Feynman retelling — plain words mein bolo

Ek matrix ek machine hai jo unit circle ko ellipse mein badal deti hai. Ellipse ka ek lamba axis aur ek chhota axis hota hai — dikhne mein sirf yahi special directions hain. Mujhe jaanna hai ki kaun se input arrows un axes par gaye aur kitna badhke gaye. Raw matrix se seedha poochna zyada mushkil hai, isliye mein $A^{⊤} A$ banata hoon, jiske paas guaranteed perpendicular un-rotated arrows $v_{i}$ ka set hota hai (yahi symmetry kharidte waqt milta hai). Unke scaling numbers $λ_{i} \geq 0$ hain; mein true stretches $σ_{i}$ paane ke liye square roots leta hoon. Har $v_{i}$ ko $A$ ke through push karke aur length ek par rescale karke output axes $u_{i}$ milte hain — aur kyunki mein unhe is tarah define karta hoon, unke signs aur pairing automatically sahi aa jaate hain. Jo bhi output directions missing hain unhe Gram–Schmidt se pad out karta hoon. Single fact " $A$ sends $v_{i}$ to $σ_{i} u_{i}$ " ko column by column assemble karke, aur ek rotation undo karke, $A = U Σ V^{⊤}$ milta hai: turn, stretch, turn. Zero stretches ka matlab sirf yeh hai ki kuch input arrows ek point par crush ho gaye — woh null space hai, aur theorem bina kisi shikayat ke ise absorb kar leta hai.

Recall

$A$ ki jagah $A^{⊤} A$ ke through detour kyon lete hain? ::: Kyunki $A^{⊤} A$ hamesha symmetric aur PSD hoti hai, isliye Spectral Theorem perpendicular eigen-arrows aur non-negative eigenvalues guarantee karta hai — $A$ khud aisi koi guarantee nahi deta. Kaun sa single fact, columns mein stack hoke, poora SVD deta hai? ::: $A v_{i} = σ_{i} u_{i}$ sabhi $i$ ke liye, jo $A V = U Σ$ mein stack hota hai, isliye $A = U Σ V^{⊤}$ . Unit circle kis geometric object par map hoti hai, aur uske axes kya hain? ::: Ek ellipse par; uske semi-axis lengths singular values $σ_{i}$ hain aur axis directions left singular vectors $u_{i}$ hain.