Least squares — normal equations, QR approach: Visual walkthrough

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

Step 1 — Vo vectors jo hamare paas hain

KYA. Humare paas kuch "measurements" hain jo ek lambi list of numbers $b$ mein stack ki gayi hain, aur ek machine $A$ jo unknown dials $x$ ko ek prediction $A x$ mein badalta hai.

Ek vector bas ek arrow hai: numbers ki ek list jo kisi direction mein point bhi karta hai. $b = (b_{1}, b_{2}, \dots, b_{m})$ ek point hai $m$ -dimensional space mein.
$A$ ek matrix hai: numbers ki ek rectangular grid jisme $m$ rows aur $n$ columns hain, likha jaata hai $A \in R^{m \times n}$ . "Tall" matlab $m > n$ — unknowns (columns) se zyada equations (rows).
$x = (x_{1}, \dots, x_{n})$ wo unknowns hain — wo dials jo hum twist kar sakte hain.

KYUN. Hum chahte hain $A x = b$ exactly. Lekin jab equations dials se zyada hon, target $b$ aksar hit nahi ho sakta. Isliye "as close as possible" define karna zaroori hai chase karne se pehle.

PICTURE. Figure mein, $b$ (plum) space mein float kar raha hai. Jab hum dials $x$ twist karte hain, $A x$ (orange) ki tip sirf ek flat sheet tak pahunch sakti hai — $b$ ko kabhi nahi chhoo sakti.

Figure — Least squares — normal equations, QR approach

Step 2 — $A x$ actually kahan ja sakta hai? (column space)

KYA. $A$ ko uske columns $a_{1}, \dots, a_{n}$ mein split karo (har column khud $m$ -space mein ek arrow hai). Tab $A x = x_{1} col 1 a_{1} + x_{2} col 2 a_{2} + \dots + x_{n} col n a_{n} .$ Yahan har term ek column-arrow ko ek dial number se scale karta hai aur unhe add karta hai. Dials twist karna columns ke saare possible mixtures ko sweep out karta hai.

Saare mixtures ka woh set column space $Col (A)$ hai — dekho Column Space and Rank. Yeh origin se guzarta hua ek flat sheet (ek subspace) hai.

KYUN. Chahe kuch bhi karein, $A x$ isi sheet ke andar rehta hai. Isliye " $b$ ke sabse kareeb pahunchne wala point" matlab "sheet ka $b$ ke sabse kareeb point." Yeh ek algebra problem ko geometry problem mein badal deta hai.

PICTURE. Do columns $a_{1}$ (teal) aur $a_{2}$ (orange) ek tilted plane span karte hain. Har reachable prediction $A x$ us plane par koi dot hai; $b$ uske upar hover kar raha hai.

Step 3 — "Closest" matlab sabse chhota arrow — kaise measure karein?

KYA. Target aur prediction ke beech ka gap residual hai: $r = target b - prediction A x .$ Iski length Euclidean norm hai $∥ r ∥ = r_{1}^{2} + r_{2}^{2} + \dots + r_{m}^{2} .$ Square root ke andar har miss $r_{i}$ ko square kiya jaata hai (taaki signs cancel na ho sakein) aur sum kiya jaata hai — yeh bas Pythagoras hai $m$ dimensions mein.

Length ki jagah length square kyun minimise karein? Hum $∥ r ∥^{2}$ minimise karenge (square root chhod denge). YEH LEGAL AUR ACHHA KYUN HAI? Kyunki $∥ r ∥^{2} = r_{1}^{2} + \dots + r_{m}^{2}$ entries mein ek plain polynomial hai — ek smooth, gently curved bowl jiska minimum hum clean linear algebra se nikal sakte hain, bina koi square root uthaye. Aur kyunki squaring lengths par ek increasing function hai ( $\geq 0$ ), jo wahi $x$ length ko smallest banata hai woh uske square ko bhi smallest banata hai — square minimise karne se hum kuch nahi kho rahe.

PICTURE. Dekho residual arrow (plum) shrink aur swing karta hai jaise prediction dot plane par slide karta hai. Ek position hai jahan woh sabse chhota hai.

Step 4 — Sabse chhota arrow wahi hai jo perpendicular ho

KYA. Claim: residual tab sabse chhota hota hai jab woh plane $Col (A)$ par perpendicular khada ho. Yeh Orthogonal Projection ke peeche ka key geometric fact hai.

KYUN. Suppose residual thoda sa bhi plane ke along jhuk jaaye. Tab woh jhukaa hua component ek aisi direction mein point karta hai jo hum actually reach kar sakte hain (woh $Col (A)$ ke andar hai). Prediction dot ko us direction mein thoda sa slide karo aur miss chhoti ho jaati hai — matlab hum minimum par nahi the. Ek hi arrow hai jise tum plane ke andar slide karke chhota nahi kar sakte — woh jo plane mein zero component rakhta hai — yaani seedha upar, perpendicular.

PICTURE. Do candidate residuals: ek tilted wala (abhi bhi chhota ho sakta hai, orange dashes) aur perpendicular winner (plum). Right-angle mark dikhata hai ki winner plane se $9 0^{\circ}$ par mil raha hai.

Step 5 — "Perpendicular" ko equations mein badalna

KYA. "Plane ke perpendicular" matlab har spanning column $a_{j}$ ke perpendicular. Do arrows perpendicular hote hain jab unka dot product zero ho — dot product $a_{j}^{⊤} r = a_{1 j} r_{1} + \dots + a_{mj} r_{m}$ measure karta hai ki woh kitna line up karte hain; zero matlab bilkul line up nahi karte.

$column j as a row a_{j}^{⊤} r, the residual (b - A \hat{x}) = 0 for every j = 1, \dots, n .$

KYUN. Ek plane apne spanning arrows se completely pin down hota hai. Agar $r$ har column ke perpendicular hai, toh woh unke har mixture ke bhi perpendicular hai — poore plane ke. Isliye $n$ chhoti equations geometry ko exactly capture karti hain.

PICTURE. Residual $a_{1}$ aur $a_{2}$ dono ke saath simultaneously right angle banata hai — do right-angle marks.

Step 6 — Equations stack karo: Normal Equations appear hoti hain

KYA. Saari $n$ dot-product equations ek line mein likhne ka matlab hai columns ko $A^{⊤}$ ki rows ke roop mein stack karna (transpose, $A$ ulta kiya hua taaki uske columns rows ban jaayein): $A^{⊤} (b - A \hat{x}) = 0 .$ $A^{⊤}$ ko subtraction par distribute karo: $target, seen by columns A^{⊤} b - prediction, seen by columns A^{⊤} A \hat{x} = 0 .$

Hum distribute kyun kar sakte hain? Kyunki matrix multiplication addition par distribute karta hai, $A^{⊤} (u - v) = A^{⊤} u - A^{⊤} v$ — ek sum ko multiply karna waise hi hai jaise har piece ko multiply karo aur combine karo. Yahan yeh single perpendicularity statement ko "target part" $A^{⊤} b$ aur "prediction part" $A^{⊤} A \hat{x}$ mein split karne deta hai jise hum alag alag rearrange kar sakte hain. Ek term ko doosri taraf move karo: $A^{⊤} A \hat{x} = A^{⊤} b$

Term by term: $A^{⊤} A$ ek chhota $n \times n$ square matrix hai (iska entry $(i, j)$ do columns ka dot product $a_{i}^{⊤} a_{j}$ hai); $A^{⊤} b$ ek chhota $n$ -vector hai (entry $j$ hai $a_{j}^{⊤} b$ ). Humne ek tall impossible system ko ek short square solvable mein badal diya.

KYUN. Yeh ab $n$ equations hain $n$ unknowns mein — square, aur (jab columns independent hain) uniquely solvable.

PICTURE. Tall $A$ compact square $A^{⊤} A$ mein collapse ho jaata hai; diagram shrink dikhata hai.

Step 7 — QR shortcut (same answer, safer arithmetic)

KYA. $A^{⊤} A$ banane ki jagah, $A = QR$ factor karo (QR Factorization / Gram-Schmidt Process se), jahan $Q$ ke orthonormal columns hain ( $Q^{⊤} Q = I$ , identity) aur $R$ upper triangular hai (diagonal ke neeche zeros). Normal equations mein substitute karo: $(QR)^{⊤} (QR) \hat{x} = (QR)^{⊤} b \Rightarrow R^{⊤} = I Q^{⊤} Q R \hat{x} = R^{⊤} Q^{⊤} b \Rightarrow R^{⊤} R \hat{x} = R^{⊤} Q^{⊤} b .$

$R^{⊤}$ kyun cancel kar sakte hain. Full-column-rank $A$ ke thin (reduced) QR mein, matrix $R$ $n \times n$ square hai, aur uske diagonal entries Gram–Schmidt ke dauran produce hue nonzero lengths hain — isliye $det R \neq = 0$ aur $R$ invertible hai. Invertible matrices ka product invertible hota hai, isliye $R^{⊤}$ bhi invertible hai. Dono sides ko left mein $(R^{⊤})^{- 1}$ multiply karna use legally hata deta hai: $R \hat{x} = Q^{⊤} b$

Term by term: $Q^{⊤} b$ $b$ ke coordinates perfect right-angle frame $Q$ mein read karta hai; $R$ ka triangular hona matlab last unknown akela nikal aata hai, phir next back-substitution se.

KYUN bother karein? Pehle, "safer" ka matlab kya hai? $A$ machine ko imagine karo jo space ko stretch karti hai: kuch directions ko bahut stretch karti hai aur kuch ko thoda. $A$ ki ek singular value aisi ek stretch factor hai — woh amount jitna $A$ ek particular unit input direction ko lengthens karta hai (sabse bada, $σ_{m a x}$ , woh zyada se zyada hai jitna $A$ kabhi ek unit arrow ko stretch kar sakta hai; sabse chhota, $σ_{m i n}$ , sabse kam). Condition number $κ (A) = σ_{m a x} / σ_{m i n}$ (dekho Condition Number) sabse badi aur sabse chhoti stretch ka ratio hai — ek single number jo measure karta hai matrix kitna rounding error amplify karta hai. Bada $κ$ = touchy arithmetic. Normal equations ki dikkat yeh hai ki $A^{⊤} A$ banana har singular value ko square kar deta hai (iske stretch factors $σ_{i}^{2}$ hain), isliye $κ (A^{⊤} A) = κ (A)^{2}$ : ek mildly touchy $A$ badly touchy ho jaata hai. QR kabhi $A^{⊤} A$ nahi banata, isliye sensitivity $κ (A)$ par rehti hai — jabki identical $\hat{x}$ deta hai.

PICTURE. $A$ ke messy tilted columns $Q$ ke clean perpendicular axes mein seedhe ho jaate hain; square axes par project karna effortless hai.

Step 8 — Har case, saaf split kiya gaya

KYA. Kuch chhootne na paaye isliye, do independent yes/no questions cross karo:

Independent columns? (full column rank vs rank-deficient) — decide karta hai ki $A^{⊤} A$ invertible hai ya nahi.
Kya $b$ reachable hai? ( $b \in Col (A)$ vs nahi) — decide karta hai ki sabse chhota residual exactly $0$ hai ya sirf nonzero.

Isse chaar boxes milte hain, sab covered:

	$b$ reachable ( $r = 0$ )	$b$ unreachable ( $r \neq = 0$ )
Independent columns	Unique $\hat{x}$ jo $A \hat{x} = b$ exactly solve karta hai; least squares exact solution reproduce karta hai.	Unique $\hat{x} = (A^{⊤} A)^{- 1} A^{⊤} b$ ; healthy projection case.
Dependent columns	Residual $0$ hai, lekin infinitely many $\hat{x}$ ise dete hain — exact solutions ki puri flat family.	Infinitely many minimisers jo saare ek hi nonzero best shadow $A \hat{x}$ share karte hain.

KYUN. Yeh chaar boxes mutually exclusive hain aur milke har possibility exhaust karte hain (columns independent ya nahi $\times$ target reachable ya nahi), isliye koi reader aisa scenario nahi hit kar sakta jo humne skip kiya ho.

Zero degenerate limit ( $A = 0$ ). Yeh "dependent columns" row mein baithta hai: prediction origin par stuck hai, residual bas $b$ hai, aur koi bhi $\hat{x}$ ek minimiser hai. Fit karne ke liye kuch nahi.

Jab bhi koi row "infinitely many" kehti hai, sabse fair, canonical choice hai sabse chhota $\hat{x}$ , jo Pseudoinverse (Moore-Penrose) deta hai.

PICTURE. Left: fat healthy plane, unique drop (independent columns). Right: collapsed thin plane, dial-settings ki puri line ek hi shadow par land karti hai (dependent columns).

Ek-picture summary

Upar sab kuch ek gesture hai: $b$ ko perpendicularly reachable predictions ke plane par drop karo; us drop ka foot $A \hat{x}$ hai; drop-arrow residual hai.

Neeche ka final schematic retelling ko ek flow mein distil karta hai: target → drop → foot → miss, with the two formulas hanging off it.

Recall Feynman retelling — saara walkthrough plain words mein

Tum ek floating dot $b$ ko hit karne ki koshish kar rahe ho, lekin tumhari gun sirf ek tilted table top (column space) par fire kar sakti hai — dot uske upar hang kar rahi hai, pahunch se bahar. Isliye tum table par woh spot dhundhte ho jo dot ke sabse kareeb ho. Kaunsa spot? Dot se table tak seedha ek plumb line drop karo; jahan woh land kare woh tumhara best shot $A \hat{x}$ hai, aur plumb line khud miss hai (residual). "Seedha neeche" poora raaz hai: ek plumb line table ke right angles par khada hota hai, isliye uski miss un saari directions ke right angles par hai jinhe tum aim kar sakte the. "Har column ke right angles par" symbols mein likhna hai $A^{⊤} (b - A \hat{x}) = 0$ , jo tidy hokar $A^{⊤} A \hat{x} = A^{⊤} b$ ban jaata hai. QR wahi drop hai lekin cleaner measuring sticks ke saath (perfect right-angle axes $Q$ ), isliye tumhara calculator arithmetic mein nahi fumble karta: $R \hat{x} = Q^{⊤} b$ . Aur agar table secretly sirf ek line hai (dependent columns), toh bahut saare aim-settings ek hi spot par land karte hain — tum sabse gentle wala choose karte ho.

Active Recall

Sabse chhota residual perpendicular kyun hota hai?

Residual ka koi bhi component jo plane ke andar lie karta hai, prediction ko slide karke remove kiya ja sakta hai, miss ko chhota karte hue — isliye minimum par residual ka in-plane component zero hota hai, yaani woh perpendicular hota hai.

"Residual ⊥ har column" ko ek matrix equation mein badlo.

A^{⊤} (b - A \hat{x}) = 0

, yaani

A^{⊤} A \hat{x} = A^{⊤} b

ar g min_{x} g (x)

ka matlab kya hai?

Woh input

x

g

ko smallest banata hai (

g

ki smallest value nahi).

QR derivation mein

R^{⊤}

kyun cancel kar sakte hain?

Full-rank

A

ke thin QR mein,

R

square hai nonzero diagonal ke saath, isliye invertible hai; toh

R^{⊤}

invertible hai aur multiply karke hata sakte hain.

Singular value kya hoti hai, aur yahan kyun matter karti hai?

A

ka ek stretch factor;

κ (A) = σ_{m a x} / σ_{m i n}

, aur

A^{⊤} A

banana har

σ_{i}

ko square kar deta hai, isliye

κ (A^{⊤} A) = κ (A)^{2}

Jab

A

ke columns dependent hon toh kya hota hai?

A^{⊤} A

singular ho jaata hai; infinitely many

\hat{x}

residual minimize karte hain, aur minimum-norm wala pseudoinverse se aata hai.