Foundations — Least squares — normal equations, QR approach

4.5.41 · D1 · Maths › Linear Algebra (Full) › Least squares — normal equations, QR approach

Parent note mein koi bhi boxed formula padhne se pehle, aapko har letter ka kuch aisa matlab pata hona chahiye jo aap picture kar sako. Yeh page har symbol ko kuch bhi nahi se build karta hai, ek aisi order mein jahan har ek sirf pehle wale pe lean karta hai. Neeche kuch bhi aisa symbol use nahi karta jo kisi pehle section ne already define na kiya ho.

1. Numbers stack kiye hue — a vector

Picture. 2 components wala vector ek flat sheet of paper pe ek arrow hai (2D). 3 components ke saath yeh ek room mein arrow hai (3D). $m$ components ke saath yeh ek aisi space mein arrow hai jo hum draw nahi kar sakte lekin phir bhi reason kar sakte hain, jise ${\mathbb{R}}^m$ kehte hain — "$m$ real numbers ki saari lists".

Topic ko yeh kyun chahiye. Aapka data (woh measurements jo aap fit karna chahte ho) ek vector ban jaata hai, aur jo answer aap solve kar rahe ho woh ek aur vector ban jaata hai. Sab kuch arrows hai — toh yeh pehli brick hai.

2. Arrow kitna lamba hai — the norm

Picture. 2D mein, components $(3,4)$ wala ek arrow ek right triangle ka hypotenuse hai jiske legs $3$ aur $4$ hain, toh uski length hai $\sqrt{3^2+4^2}=5$. Higher dimensions mein hum wahi karte hain — har component ko square karo, add karo, square-root lo.

Topic ko yeh kyun chahiye. "Closest" ka matlab hai "shortest distance". Do arrow-tips ke beech ki distance unhe jodne wale arrow ki length hai. Least squares is length ko minimise karta hai. Woh chota "$2$" $\Vert \cdot {\Vert }_2$ mein sirf yeh label karta hai ki kaunsi kind of length hai (ordinary Euclidean wali).

3. Direction agreement — the dot product

Picture. Dot product measure karta hai ki do arrows kitna ek hi taraf point karte hain.

• Same direction → bada positive number.
• Perpendicular ($90°$ pe) → exactly zero.
• Opposite → negative.

Topic ko yeh kyun chahiye. Least squares ka poora geometric heart yeh hai ki "miss-arrow reachable points ke menu ke perpendicular hai". Perpendicular detect hota hai dot product ke zero hone se — aur zero dot products exactly wahi hain jo geometry ko equations mein badlenge do sections baad.

4. Arrows pe acting karta number ka grid — the matrix

Picture. Columns ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n$ ko "ingredient" arrows ka set samjho. Numbers $x_1,\dots ,x_n$ jo $\mathbf{x}$ ke andar hain woh har ingredient ki matra hain. $A\mathbf{x}$ woh arrow hai jo aap unhe mix karke banate ho.

"Tall" kyun? Hamare problem mein $m\ge n$: zyada rows (equations / data points) columns se (unknowns). Yeh ek overdetermined system hai — bahut zyada demands, usually saari ek saath satisfy karna impossible hai.

5. Jab ingredients wasteful nahi hote — independent columns aur rank

Picture. Do arrows genuinely alag directions mein point karte hue poora plane sweep karte hain. Lekin agar ek teesra arrow usi plane ke andar flat pada ho, toh woh kuch naya nahi add karta — woh "dependent" hai. Full column rank ka matlab hai har ingredient arrow kahin aisa point karta hai jahan baaki pahunch nahi sakte.

Topic ko yeh kyun chahiye. Yeh make-or-break condition hai. Agar columns independent hain, toh best-fit answer unique hoga — exactly ek recipe $\mathbf{x}$ hai jo closest point pe land karta hai. Agar koi column redundant hai, infinitely many recipes same closest point dete hain, aur answer unique nahi rehta (tab aap Pseudoinverse (Moore-Penrose) ki taraf jaate ho). Yeh flag yaad rakho; Section 8 mein exactly yahi key matrix ko invertible banata hai. Zyada detail Column Space and Rank mein.

6. Har reachable point — the column space

Picture. 3D mein do independent column arrows ke saath, unke saare mixes ek flat plane sweep karte hain origin se guzarte hue. Woh plane reachable points ka "menu" hai. Target $\mathbf{b}$ usually plane ke upar float karta hai — menu pe nahi.

Topic ko yeh kyun chahiye. "Koi exact solution nahi hai" ka exactly yahi matlab hai ki "$\mathbf{b}$ $\text{Col}(A)$ mein nahi hai". Hum jo best kar sakte hain woh hai plane ke upar woh point dhundhna jo $\mathbf{b}$ ke sabse kareeb ho.

7. Plane pe nearest point — orthogonal projection

Picture. Ek pencil pakdo (woh $\mathbf{b}$ hai) table ke upar (plane). Seedha upar se aane wali roshni se pada shadow projection $\hat{\mathbf{b}}=A\hat{\mathbf{x}}$ hai. Chhota arrow shadow se pencil ki tip tak residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ hai, aur woh seedha upar khada hai, table ke perpendicular.

Seedha upar best kyun hai. Table pe koi bhi doosra point zyada door hai — uska connecting arrow ek slanted hypotenuse hoga, aur hypotenuse hamesha vertical leg se lamba hota hai. Isliye minimum-distance point perpendicular wala hota hai. Poori detail Orthogonal Projection mein hai.

8. "Perpendicular" se normal equations tak

Ab har symbol define ho chuka hai, toh hum dekh sakte hain ki geometry algebra mein kaise badlti hai — yeh woh step hai jo parent note box karta hai, yahan scratch se build kiya gaya.

Step 1 — "perpendicular" ko dot products ke roop mein likho. Residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ plane ke seedha upar khada hai. Plane ke perpendicular khade rehne ka matlab hai har ingredient arrow ${\mathbf{a}}_j$ ke perpendicular hona jo plane build karta hai. Section 3 ka dot product use karke, "perpendicular" hai "dot product zero": ${\mathbf{a}}_j^{\top }(\mathbf{b}-A\hat{\mathbf{x}})=0\text{har column }j=1,\dots ,n\text{ ke liye.}$

Step 2 — $n$ alag equations ko ek mein stack karo. Hamare paas $n$ statements hain, har column ke liye ek. Rows ${\mathbf{a}}_1^{\top },\dots ,{\mathbf{a}}_n^{\top }$ ko ek doosre ke upar stack karne se exactly transpose $A^{\top }$ rebuild hota hai (transpose columns ko rows mein badalta hai — Section 3). Toh dot-product-zero conditions ka poora batch ek single matrix equation hai: $A^{\top }(\mathbf{b}-A\hat{\mathbf{x}})=0.$

Step 3 — multiply out karo. $A^{\top }$ ko bracket ke across distribute karo aur $\mathbf{b}$ term ko doosri side le jaao: $A^{\top }\mathbf{b}-A^{\top }A\hat{\mathbf{x}}=0⟹\boxed{A^{\top }A\hat{\mathbf{x}}=A^{\top }\mathbf{b}}$

Yeh normal equations hain. "Normal" word sirf "perpendicular" ka ek purana synonym hai — poori cheez usi ek right angle se born hai.

9. Ek ideal coordinate grid — orthonormal columns aur $Q$

Picture. Orthonormal columns graph paper ke clean $x$/$y$/$z$ axes jaisi hain: unit length, right angles pe milte hue. Aisi grid pe project karna effortless hai — koi stretching ya shearing nahi hai jo sunhani pade.

10. Numbers ki ek staircase — upper-triangular $R$

Picture. Kyunki bottom-left empty hai, last equation mein sirf last unknown aata hai. Usse solve karo, answer upar feed karo, agla solve karo — yeh bottom-to-top zigzag back-substitution kehlaata hai.

Topic ko yeh kyun chahiye. QR route least squares ko $R\hat{\mathbf{x}}=Q^{\top }\mathbf{b}$ mein reduce karta hai. Kyunki $R$ triangular hai, yeh back-substitution se instantly solve ho jaata hai, $A^{\top }A$ banane ke error-amplifying step se bachate hue (ek danger jo Condition Number se measure hota hai).

11. Foundations kaise connect hoti hain

Neeche ka map top-to-bottom ek dependency chain ki tarah padha jaata hai: har box ek tool hai jo aapke paas hona chahiye pehle us box ke liye jise woh point karta hai. Dono paths (normal equations aur QR) same answer pe milte hain.

Full symbol glossary (quick reference)

Equipment checklist

Apni readiness khud test karo. Neeche har line prompt ::: answer ke roop mein likhi hai — is vault mein use hone wala ek reveal format: sirf left side padho, apna answer zor se bolo, phir right side uncover karo check karne ke liye. Agar koi bhi answer asaani se nahi aata, toh parent note pe jaane se pehle uska section dobara padho.

Jab tak har line asaani se aane lage, parent note mein boxed formulas plain sentences ki tarah padhenge. Related deep applications: Linear Regression, Pseudoinverse (Moore-Penrose).