Gram-Schmidt orthogonalization — algorithm: Visual walkthrough

4.5.35 · D2 · Maths › Linear Algebra (Full) › Gram-Schmidt orthogonalization — algorithm

Step 0 — Ek vector kya hota hai, aur "kisi direction mein jhukna" matlab kya?

KYA. Ek vector ek arrow hai jiske paas length aur direction dono hain. Plane mein hum ise numbers ki ek pair $v = (v_{x}, v_{y})$ ki tarah likhte hain: $v_{x}$ steps right jao, phir $v_{y}$ steps upar, aur tumhari pencil ki tip wahan point karti hai jahan arrow jaata hai.

YE YAHAN SE KYUN SHURU KAREIN. Jo bhi aage aane wala hai, woh sab is baare mein hai ki ek arrow doosre ke saath kitna jhukta hai. "Jhukav" measure karne se pehle humein ek aisa number chahiye jo use capture kare. Woh number hai inner product (jise dot product bhi kehte hain).

PICTURE. Do arrows ek hi tail share karte hain. Unke beech ka angle hi woh cheez hai jo $⟨ a, b ⟩$ secretly measure karta hai — aur yeh exactly $0$ hota hai jab woh angle $9 0^{\circ}$ ho.

Figure — Gram-Schmidt orthogonalization — algorithm

Recall "

$⟨ a, b ⟩ = 0$ matlab perpendicular" believable kyun hai? $⟨ a, b ⟩ = ∥ a ∥ ∥ b ∥ cos θ$ , jahan $θ$ unke beech ka angle hai. Perpendicular matlab $θ = 9 0^{\circ}$ , aur $cos 9 0^{\circ} = 0$ , toh poori cheez $0$ ho jaati hai. ::: Cosine arithmetic aur geometry ke beech ka bridge hai.

Step 1 — Shadow: ek arrow ko doosre par project karna

KYA. Ek clean reference direction $u$ par seedha neeche se light maaro. Messy arrow $v$ us line par ek shadow daalega jahan $u$ hai. Woh shadow, $u$ ki ek scaled copy $c u$ hai. Humein woh ek number $c$ dhundhna hai.

YEH TOOL KYUN, KUCH AUR KYUN NAHI. Hum try kar sakte hain "ankhon se andhaza lagaana" ki $v$ kitna $u$ ki taraf pahunchta hai — lekin Gram–Schmidt ko exact amount chahiye taaki jo bhi bachta hai woh perfectly perpendicular ho. Aisa karne wala sirf ek $c$ hai, aur inner product use hamare haath mein de deta hai. Yeh akela operation hai Orthogonal projection, poore algorithm ki dhadkan.

PICTURE. Shadow $c u$ line par land karta hai; $v$ ki tip se dashed drop $u$ se right angle par milti hai. Bacha hua arrow $r = v - c u$ wahi dashed drop hai — aur woh $u$ ke perpendicular hai.

Ab chalte hain right angle ko force karte hain aur $c$ solve karte hain.

Step 2 — Bacha hua rakho, aur woh guaranteed perpendicular hai

KYA. $v$ se shadow subtract karo. Jo bachta hai, $r = v - proj_{u} (v),$ woh $v$ ka woh hissa hai jiska $u$ se koi lena-dena nahi tha.

KYUN. Humne $c$ exactly isliye choose kiya tha taaki $⟨ r, u ⟩ = 0$ ho. Yeh luck nahi hai — yahi woh equation thi jo humne solve ki. Toh $r$ ek bilkul naye, independent direction mein point karta hai, $u$ ke saath ek clean right angle par.

PICTURE. Dekho $v$ do arrows mein split hota hai jo head-to-tail place hain: $u$ ke saath horizontal shadow, aur vertical bacha hua $r$ exactly $9 0^{\circ}$ par climb karta hua. Dono shadows add back up hokar $v$ bante hain.

Step 3 — Pehla worked pair: $v_{1} = (3, 1), v_{2} = (2, 2)$

KYA. Bilkul pehle vector ko as-is lo — ise koi cleaning nahi chahiye kyunki abhi kuch nahi hai jiske perpendicular hona ho: $u_{1} = v_{1} = (3, 1) .$ Phir $v_{2}$ ko $u_{1}$ ke against clean karo.

KYUN. Sirf ek settled direction ke saath, recursion mein ek hi term hai. Hum $v_{2}$ ka $u_{1}$ par shadow compute karte hain aur subtract karte hain.

$2 \cdot 3 + 2 \cdot 1 = 8 ⟨ v_{2}, u_{1} ⟩, 9 + 1 = 10 ⟨ u_{1}, u_{1} ⟩, c = \frac{8}{10} .$

$u_{2} = (2, 2) - \frac{8}{10} (3, 1) = (2, 2) - (2.4, 0.8) = (- 0.4, 1.2) .$

$(2, 2)$ — messy input $v_{2}$ .
$(2.4, 0.8)$ — $u_{1}$ par uska shadow.
$(- 0.4, 1.2)$ — pure bacha hua, aur $⟨ u_{1}, u_{2} ⟩ = 3 (- 0.4) + 1 (1.2) = 0$ . ✅

PICTURE. $u_{1}$ shallow slope par baitha hai; $v_{2}$ up-right point karta hai; amber shadow $u_{1}$ par land karta hai; cyan bacha hua $u_{2}$ perpendicular shoot karta hai.

Step 4 — Hum $u_{j}$ se kyun subtract karte hain, $v_{j}$ se kyun nahi

WHAT. Recursion mein shadows already-orthogonalized $u_{j}$ par cast hote hain, na ki original messy $v_{j}$ par.

KYUN. General recursion lo aur ise ek earlier $u_{i}$ se dot karo (jahan $i < k$ ):

= \langle v_k,u_i\rangle - \sum_{j<k}\frac{\langle v_k,u_j\rangle}{\langle u_j,u_j\rangle}\underbrace{\langle u_j,u_i\rangle}_{\text{= }0\text{ unless }j=i}.$$ Kyunki $u$ *mutually perpendicular* hain, har cross term $\langle u_j,u_i\rangle$ mar jaata hai sivaaye us ek ke jahan $j=i$ ho. Woh surviving term pehle wale piece ko exactly cancel karta hai: $$= \langle v_k,u_i\rangle - \frac{\langle v_k,u_i\rangle}{\langle u_i,u_i\rangle}\langle u_i,u_i\rangle = 0.$$ Agar hum raw $v_j$ use karte, toh cross terms $\langle v_j,v_i\rangle$ **vanish nahi hote** — cancellation collapse ho jaata aur $u_k$ tilted reh jaata, perpendicular nahi hota. **PICTURE.** Left panel: clean orthogonal $u_1,u_2$ par shadows subtract karne se bacha hua seedha khada rehta hai. Right panel: tangled $v_1,v_2$ par subtract karne se bacha hua abhi bhi lean karta hai — method fail ho jaata hai. ![[deepdives/dd-maths-4.5.35-d2-s05.png]] --- ## Step 5 — $\mathbb{R}^3$ mein ek saath do subtractions **KYA.** $v_1=(1,1,0),\ v_2=(1,0,1),\ v_3=(0,1,1)$ ke saath, teesre vector ko **dono** settled directions $u_1$ aur $u_2$ par apna shadow kho dena chahiye. - $u_1=(1,1,0)$. - $u_2 = v_2-\frac{\langle v_2,u_1\rangle}{\langle u_1,u_1\rangle}u_1=(1,0,1)-\frac12(1,1,0)=\left(\tfrac12,-\tfrac12,1\right).$ - $u_3$ ke liye, do overlaps: $$\frac{\langle v_3,u_1\rangle}{\langle u_1,u_1\rangle}=\frac12,\qquad \frac{\langle v_3,u_2\rangle}{\langle u_2,u_2\rangle}=\frac{1/2}{3/2}=\frac13.$$ $$u_3=(0,1,1)-\tfrac12(1,1,0)-\tfrac13\left(\tfrac12,-\tfrac12,1\right)=\left(-\tfrac23,\tfrac23,\tfrac23\right).$$ **DO TERMS KYUN.** Do already-clean directions hain jinke perpendicular hona hai, toh hum do shadows erase karte hain. Har subtraction Step 2 hai, independently kiya gaya — aur *kyunki* $u_1\perp u_2$, ek shadow hatane se doosra wapas nahi aata. **Check:** $\langle u_3,u_1\rangle=-\tfrac23+\tfrac23+0=0$ aur $\langle u_3,u_2\rangle=-\tfrac13-\tfrac13+\tfrac23=0$. ✅ **PICTURE.** 3D mein, $v_3$ $u_1$ aur $u_2$ se bane plane par do shadows drop karta hai; dono hatane par $u_3$ us plane se seedha bahar point karta hai. ![[deepdives/dd-maths-4.5.35-d2-s06.png]] --- ## Step 6 — Normalize: har ek ko unit length mein shrink karo **KYA.** Ab hamare paas alag-alag lengths ke perpendicular arrows hain. [[Orthonormal basis]] banane ke liye, har ek ko uski apni length se divide karo: $$e_k=\frac{u_k}{\lVert u_k\rVert},\qquad \lVert u_k\rVert=\sqrt{\langle u_k,u_k\rangle}.$$ Step 3 ke liye: $\lVert u_1\rVert=\sqrt{10}$, $\lVert u_2\rVert=\sqrt{1.6}$, jo deta hai $$e_1=\tfrac{1}{\sqrt{10}}(3,1),\qquad e_2=\tfrac{1}{\sqrt{1.6}}(-0.4,1.2).$$ **KYUN.** Scaling se direction nahi badlti, toh perpendicularity survive karti hai. Unit length hi woh cheez hai jo projections ke denominators hata deta hai aur columns ko [[QR decomposition]] ke $Q$ ka hissa banata hai. **PICTURE.** Pehle jaisa hi right angle, lekin ab dono arrows exactly unit circle tak pahunchte hain. ![[deepdives/dd-maths-4.5.35-d2-s07.png]] --- ## Step 7 — Degenerate case: ek dependent input zero ho jaata hai **KYA.** Maan lo $v_2$ bas $v_1$ ki ek stretched copy hai, jaise $v_2=2v_1$. Tab $v_2$ poora shadow hai — uski poori self $u_1$ ke along lean karti hai. **KYUN.** Shadow $v_2$ ke equal hai, toh $$u_2 = v_2-\operatorname{proj}_{u_1}(v_2)=v_2-v_2=\mathbf{0}.$$ Ek **zero vector** ka koi direction nahi hota aur length $0$ hoti hai, toh normalize nahi kar sakte (zero se division). Gram–Schmidt tumhe *bata raha hai* ki input independent nahi tha — dekho [[Linear independence]]. Yeh bug nahi hai; yeh ek built-in detector hai. **PICTURE.** $v_2$ $u_1$ ke upar flat lie karta hai; uska shadow use poora cover karta hai; bacha hua origin par ek single point mein shrink ho jaata hai. ![[deepdives/dd-maths-4.5.35-d2-s08.png]] > [!mistake] Dependent vectors se nonzero $u_k$ expect karna > **Kyun sahi lagta hai:** formula abhi bhi "run" karta hai aur *kuch* return karta hai. **Fix:** woh kuch $\mathbf 0$ hai. Jab bhi $u_k=\mathbf 0$ ho, $v_k$ drop karo — usne koi naya direction nahi add kiya. Yahi woh tarika hai jisse algorithm linear dependence report karta hai. --- ## Ek-picture summary Neeche, ek hi diagram par poori derivation: messy inputs left se enter karte hain, har naya vector har settled direction par apne shadows shed karta hai, bacche hue right angles par stack up hote hain, aur normalization unhe unit circle par tuck kar deta hai. ![[deepdives/dd-maths-4.5.35-d2-s09.png]] > [!formula] Sab kuch ek line mein > $$u_1=v_1,\qquad u_k=v_k-\sum_{j<k}\frac{\langle v_k,u_j\rangle}{\langle u_j,u_j\rangle}u_j,\qquad e_k=\frac{u_k}{\lVert u_k\rVert}.$$ > [!recall]- Feynman: poora walkthrough apne shabdon mein batao > Socho flashlights aur ek wall. Pehle, main apna bilkul pehla arrow exactly as-is rakhta hoon — ise reference kaho, abhi kuch fix nahi karna. Agle arrow ke liye, main reference par neeche light maarta hoon aur dekhta hoon ki woh kaunsa shadow daalti hai; woh shadow woh part hai jo unhe share hai. Main arrow ko exactly us shadow ke jaritna wapas slide karta hoon, aur jo piece bacha hai woh ab reference ke saath perfect right angle par khada hai — yeh guaranteed hai, kyunki maine shadow ka size isliye choose kiya tha ki bacha hua perpendicular ho. Teesre arrow ke liye main same trick do baar karta hoon: pehli clean direction par uska shadow hatao aur doosri par uska shadow hatao, aur bacha hua seedha bahar nikal aata hai, dono ke perpendicular. Kyunki main hamesha *already-cleaned* arrows par shadows subtract karta hoon (raw wale nahi), shadows kabhi interfere nahi karte aur har cross-overlap cleanly cancel ho jaata hai. Agar koi arrow secretly us ek ki stretched copy thi jo mere paas pehle se hai, toh uski poori self shadow hai aur bacha hua kuch nahi rehta — algorithm ne abhi mujhe bataya ki arrows independent nahi the. Aakhir mein main har surviving arrow ko length one tak shrink karta hoon. Done: same space, sab right angles, sab unit length. Overlap hatao, bacha hua rakho. ::: Woh ek mantra hi *hai* Gram–Schmidt. --- ## Connections - [[Inner product spaces]] — $\langle\cdot,\cdot\rangle$ supply karta hai jo right angles detect karta hai - [[Orthogonal projection]] — Steps 1–2 ka shadow operation - [[Orthonormal basis]] — Step 6 ka unit-length output - [[QR decomposition]] — columns $e_k$ ban jaate hain $Q$ - [[Linear independence]] — Step 7 mein collapse iski failure detect karta hai - [[Least squares]] — orthogonal directions equations ko decouple karte hain - [[Gram-Schmidt orthogonalization — algorithm]] — parent formula jise yeh page draw karta hai