QR decomposition: Visual walkthrough — Hinglish deep dive

4.5.36 · D2 · Maths › Linear Algebra (Full) › QR decomposition

Line one se pehle, teen seedhe saade words jinhe hum poori tarah use karenge:

Hum ek chhoti si matrix use karenge $A = 101110 = [a_{1} ∣ a_{2}], a_{1} = (1, 0, 1), a_{2} = (1, 1, 0)$ apne running board example ke roop mein. 3D mein do tedhe arrows. Chalte hain, inhe seedha karte hain.

Step 1 — Pehla clean axis lagao

KYA. Hum pehle tedhe arrow $a_{1}$ ko lete hain aur use length $1$ tak shrink karte hain, uski direction wahi rakhte hain. Result ka naam rakhte hain $q_{1}$ . $q_{1} = \frac{a _{1}}{∥ a _{1} ∥}, ∥ a_{1} ∥ = a_{1}^{⊤} a_{1} = 1^{2} + 0^{2} + 1^{2} = 2 .$

$a_{1}$ — raw pehla arrow.
$∥ a_{1} ∥ = 2$ — uski length, dot product se apne aap ke saath nikali.
$2$ se divide karna — sirf length badlti hai ( $\to 1$ ); direction bilkul nahi badlti.

Toh $q_{1} = \frac{1}{2} (1, 0, 1)$ .

KYUN. Har doosra arrow $q_{1}$ ke against measure hoga. Ek ruler ki length $1$ honi chahiye pehle, tab hi tum usse measure kar sakte ho — "normalize" ka bas itna hi matlab hai.

PICTURE. Pale-yellow arrow hai $a_{1}$ ; blue arrow hai chhota hua $q_{1}$ jo uske upar bilkul sidha baith gaya hai, ab exactly ek unit lamba.

Step 2 — Doosre arrow ka shadow measure karo

KYA. $a_{2}$ ko clean karne se pehle, hum poochte hain: $a_{2}$ ka kitna hissa pehle se $q_{1}$ ki taraf point kar raha hai? Woh amount ek akela number hai, $r_{12} = q_{1}^{⊤} a_{2} = \frac{1}{2} (1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0) = \frac{1}{2} .$

$q_{1}^{⊤} a_{2}$ — dot product = " $a_{2}$ $q_{1}$ direction mein kitna pahuncha."
result $\frac{1}{2} \approx 0.707$ — us shadow ki length jo $a_{2}$ $q_{1}$ line par daalta hai.
hum ise $r_{12}$ kehte hain — yeh recipe card $R$ ka ek entry banega (row $1$ , column $2$ ).

KYUN. Dot product ko precisely isliye choose kiya gaya kyunki yeh shadow length read off karta hai. Yeh projection idea hai: $r_{12} q_{1}$ woh piece hai $a_{2}$ ka jo "pehle se explain ho gaya" hamare pehle axis se.

PICTURE. $a_{2}$ ki tip se $q_{1}$ line par ek dashed perpendicular giraao. Jahan woh land kare, wahan shadow $r_{12} q_{1}$ mark hota hai (pink).

Step 3 — Shadow subtract karo, nayi direction reveal karo

KYA. Explained piece ko mita do. Jo bacha woh $q_{1}$ ke perpendicular hona chahiye: $u_{2} = a_{2} - r_{12} q_{1} = (1, 1, 0) - \frac{1}{2} \cdot \frac{1}{2} (1, 0, 1) = (\frac{1}{2}, 1, - \frac{1}{2}) .$

$a_{2}$ — poora doosra arrow.
$r_{12} q_{1}$ — Step 2 ka shadow, ab ek real arrow mein scale back kiya.
$u_{2}$ — jo bacha, yaani $a_{2}$ ka woh hissa jo $q_{1}$ ke right angle par hai.

Check karo ki kaam kiya: $q_{1}^{⊤} u_{2} = \frac{1}{2} (\frac{1}{2} + 0 - \frac{1}{2}) = 0$ . ✓ Perpendicular, bilkul jaisa promise kiya tha.

KYUN. Shadow subtract karna Gram-Schmidt process ki poori trick hai: jo shared hai use hatao, jo naya hai use rakho. $0$ ka dot product confirm karta hai ki jo bacha woh ek bilkul naya independent direction hai.

PICTURE. Vector subtraction as a triangle: $a_{2}$ minus pink shadow deta hai green $u_{2}$ , jo $q_{1}$ line ke $9 0^{\circ}$ par khada hai.

Step 4 — Bacha hua arrow length one par shrink karo

KYA. $u_{2}$ ko unit ruler $q_{2}$ mein badlo, aur uski original length record karo: $∥ u_{2} ∥ = (\frac{1}{2})^{2} + 1^{2} + (- \frac{1}{2})^{2} = \frac{3}{2}, r_{22} = ∥ u_{2} ∥ = \frac{3}{2}, q_{2} = \frac{u _{2}}{∥ u _{2} ∥} .$

$∥ u_{2} ∥ = 3/2 \approx 1.225$ — nayi direction shrink hone se pehle kitni lambi thi.
$r_{22}$ — yeh length diagonal recipe entry ban jaati hai (row $2$ , column $2$ ).
$q_{2}$ — hamaara doosra clean axis, length $1$ , $q_{1}$ se perpendicular.

KYUN. Hum length $r_{22}$ mein store karte hain kyunki baad mein $a_{2}$ ko rebuild karne ke liye iska zaroorat padegi. Unit vector measuring ke liye hai; length reconstructing ke liye hai. Note karo ki $r_{22} > 0$ automatically — bacha hua non-zero tha kyunki hamare do arrows genuinely alag the (linearly independent).

PICTURE. Green $u_{2}$ (length $3/2$ ) shrink hokar blue unit $q_{2}$ par aa jaata hai. Ab $q_{1} ⊥ q_{2}$ : ek clean right-angle corner.

Step 5 — Recipe ko ulta padho: originals rebuild karo

KYA. Hamare paas clean axes hain $q_{1}, q_{2}$ . Ab har equation ko flip karo taaki original arrows ko clean ones ke combinations mein express kar sako: $a_{1} = ∥ a_{1} ∥ q_{1} = r_{11} q_{1}, a_{2} = r_{12} q_{1} + r_{22} q_{2} .$

$a_{1}$ sirf $q_{1}$ use karta hai — $r_{11} = ∥ a_{1} ∥ = 2$ ke saath.
$a_{2}$ $q_{1}$ (amount $r_{12}$ ) aur $q_{2}$ (amount $r_{22}$ ) use karta hai — lekin kabhi bhi koi baad waala axis nahi, kyunki $a_{2}$ ko $q_{3}$ ke exist karne se pehle hi clean kar diya gaya tha.

Recipe numbers ko ek grid $R$ mein collect karo, aur clean axes ko $Q$ mein: $Q = [q_{1} ∣ q_{2}], R = [r_{11} 0 r_{12} r_{22}] = [20 \frac{1}{2} 3/2] .$

KYUN zero (upper-triangular)? $a_{1}$ ko $q_{2}$ ke paida hone se pehle seedha kar diya gaya, isliye $q_{2}$ $a_{1}$ ki recipe mein appear nahi kar sakta — uska coefficient $0$ hone par majboor hai. Woh akela $0$ bottom-left mein wahi hai jiska matlab "upper-triangular" hai: har arrow sirf wahi axes use karta hai jo pehle se exist karte the. Yahi hai QR decomposition result, $A = QR$ .

PICTURE. $R$ as an instruction card: column $k$ tumhe exact mix batata hai $q_{1}, \dots, q_{k}$ ka jo $a_{k}$ rebuild karta hai. Bottom-left cell greyed out hai — "future axis use nahi kar sakte" rule.

Step 6 — Degenerate case: agar bacha hua zero ho toh?

KYA. Maano $a_{2}$ $a_{1}$ ki direction ki copy hoti, jaise $a_{2} = (2, 0, 2)$ . Uska shadow $q_{1}$ par poora arrow hota, toh bacha hua hoga $u_{2} = a_{2} - (q_{1}^{⊤} a_{2}) q_{1} = 0, ∥ u_{2} ∥ = 0.$

KYUN yeh QR tod deta hai. $q_{2}$ banane ke liye hum $∥ u_{2} ∥$ se divide karte hain — lekin yahan woh $0$ hai, aur zero se divide karna undefined hai. Saath hi $r_{22} = 0$ ho jaata hai, toh $R$ ki diagonal strictly positive nahi rahi. Geometrically: koi nayi direction hi nahi jisme axis plant kar sako.

Yeh rule force karta hai. QR (thin, positive diagonal ke saath) chahiye ki $A$ ke columns linearly independent hon — koi arrow doosron ka mix nahi hona chahiye. Jab woh independent hote hain, har bacha hua non-zero hota hai, har $r_{k k} > 0$ hota hai, aur poora construction safely chalta hai.

PICTURE. Do collinear yellow arrows: shadow poore doosre arrow ko kha jaata hai, kuch nahi bachta (origin par ek red dot) — woh moment jab algorithm ko rukna padta hai.

Step 7 — Sign convention: kyun hum $r_{k k} > 0$ insist karte hain

KYA. Kuch nahi roka tha hume $q_{2}$ ko ulti taraf point karne se (multiply by $- 1$ ). Agar hum karte, toh $r_{22}$ bhi sign flip karta, aur $r_{12}$ match karne ke liye shift hota — toh $A = QR$ tab bhi hold karta, lekin alag $Q$ aur $R$ ke saath.

KYUN. Ek factorization jise hum pin down nahi kar sakte, woh annoying hai. QR ko unique banane ke liye, hum demand karte hain ki $r_{k k} = ∥ u_{k} ∥ > 0 har k ke liye,$ jo guaranteed hai jab hum hamesha ek positive length se divide karte hain. Woh ek convention sign ambiguity remove kar deta hai.

PICTURE. Same corner, $q_{2}$ ke do allowed choices (up-blue vs down-pink); hum woh rakhte hain jo positive diagonal deta hai.

Ek-picture summary

Upar sab kuch, ek board par: tedhe arrows $A$ baayi taraf se "straighten & record" ke through behte hain clean frame $Q$ plus triangular recipe $R$ mein, aur unhe wapas multiply karne par $A$ reproduce hota hai.

$A (tedhe) [a_{1} ∣ a_{2}] = Q (clean frame) [q_{1} ∣ q_{2}] R (recipe, upper-triangular) [r_{11} 0 r_{12} r_{22}]$

Recall Feynman retelling — ek story ki tarah bolo

Mere paas chalkboard par do tedhe arrows the. Maine pehle wale ko pakda aur use length one tak squeeze kar diya — yahi mera pehla clean ruler hai, $q_{1}$ . Phir maine doosre arrow ko dekha aur poochha, "tum mein se kitna hissa mere ruler ki tarah hi jhuk raha hai?" Woh amount ek number hai, $r_{12}$ ; maine woh part wipe off kar diya. Jo bacha woh bilkul right angle par khada tha — maine usse bhi length one tak squeeze kiya aur use $q_{2}$ bulaya, aur likh liya ki woh kitna lamba tha ( $r_{22}$ ). Ab mere paas rulers ka ek tidy square corner hai, $Q$ . Woh chhota sa numbers ka card jo maine likha — " $a_{1}$ = itna ruler 1 ka", " $a_{2}$ = itna ruler 1 ka plus itna ruler 2 ka" — woh hai $R$ . Kyunki arrow 1 ko ruler 2 ke kabhi exist karne se pehle seedha kiya gaya tha, ruler 2 arrow 1 ki recipe mein show up nahi kar sakta, isliye $R$ ka ek corner hamesha zero hota hai — yahi triangle shape hai. Agar kabhi koi "leftover" kuch nahi nikla (arrows secretly same direction mein the), toh mujhe zero se divide karna padta, isliye main yeh game sirf genuinely-alag arrows ke saath khelta hoon aur recorded lengths ko hamesha positive rakhta hoon taaki jawab ek-of-a-kind rahe.

Recall Quick self-test

$r_{12}$ geometrically kya number hai? ::: $a_{2}$ ke shadow ki length $q_{1}$ line par, yaani $q_{1}^{⊤} a_{2}$ .
$R$ ka bottom-left zero kyun hai? ::: $a_{1}$ $q_{2}$ ke exist hone se pehle banaya jaata hai, isliye $a_{1}$ ki recipe mein $q_{2}$ ka coefficient $0$ hona zaroori hai.
Agar columns dependent hoon toh kya galat hota hai? ::: Ek leftover $u_{k} = 0$ aa jaata hai, toh $∥ u_{k} ∥ = 0$ aur hum zero se divide karte.
Kaun sa rule QR ko unique banata hai? ::: Har diagonal $r_{k k} > 0$ .

Connections

Gram-Schmidt process — yeh walkthrough hi hai Gram–Schmidt, drawn.
Orthonormal bases and projections — Step 2 ka shadow ek projection hai.
Least squares and normal equations — $Q, R$ paane ka fayda.
Householder reflections — same $A = QR$ tak pahunchne ka ek rounding-stable raasta.
Eigenvalues and the QR algorithm — isi factorization ko baar baar dohraaता hai.
LU decomposition — ek triangular sibling, clean frame ke bina.