Least squares — normal equations, QR approach

4.5.41 · Maths › Linear Algebra (Full)

Least-squares problem KYA hai?

Squared length KYU? Yeh har jagah differentiable (smooth) hota hai, jabki $∥ \cdot ∥$ zero par ek kink rakhta hai. Square ko minimise karna length ko minimise karne ke barabar hai (same minimiser), aur algebra linear rehta hai.

Normal Equations KAISE derive karte hain (scratch se)

Hum $f (x) = ∥ b - A x ∥^{2}$ ka minimum chahte hain. Do independent derivations — jo bhi samajh aaye woh lo.

Derivation 1 — Geometry (projection / orthogonality)

Set ${A x}$ column space $Col (A)$ hai, jo ek subspace hai. Ek subspace mein $b$ ke sabse karib wala point orthogonal projection hota hai. Toh residual $A$ ke har column ke perpendicular hona chahiye:

$a_{j}^{⊤} (b - A \hat{x}) = 0 for every column a_{j} .$

Yeh step kyun? Agar residual ka koi component $Col (A)$ ke andar hota, toh hum $A x$ ko us direction mein thoda move karke aur karib aa sakte — toh true minimum par residual ka zero component column space mein hota hai, yaani woh sabhi columns se orthogonal hai.

Sabhi columns ko stack karne par $A^{⊤} (b - A \hat{x}) = 0$ milta hai, isliye

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

Derivation 2 — Calculus

Expand karo: $f (x) = (b - A x)^{⊤} (b - A x) = b^{⊤} b - 2 x^{⊤} A^{⊤} b + x^{⊤} A^{⊤} A x .$ Gradient ko zero set karo (using $\nabla_{x} (x^{⊤} M x) = 2 M x$ symmetric $M = A^{⊤} A$ ke liye, aur $\nabla_{x} (x^{⊤} c) = c$ ): $\nabla f = - 2 A^{⊤} b + 2 A^{⊤} A x = 0 \Rightarrow A^{⊤} A \hat{x} = A^{⊤} b .$ Maximum nahi, minimum kyun? Hessian $2 A^{⊤} A$ positive semidefinite hai (kyunki $v^{⊤} A^{⊤} A v = ∥ A v ∥^{2} \geq 0$ ), toh critical point ek minimum hai.

QR approach KAISE kaam karta hai (aur yeh better kyun hai)

Normal equations hi use kyun nahi karte? $A^{⊤} A$ banane se condition number square ho jaata hai ( $κ (A^{⊤} A) = κ (A)^{2}$ ), jo rounding errors ko amplify karta hai. QR, $A^{⊤} A$ banane se bilkul bachta hai.

Derivation. $A = QR$ ko 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 .$ Kyunki $R$ invertible hai (full rank), $R^{⊤}$ cancel karo:

$R \hat{x} = Q^{⊤} b$

Yeh step kyun? $R$ triangular hai, toh back-substitution se solve karo — fast aur numerically stable. $A^{⊤} A$ kabhi appear hi nahi karta.

Figure — Least squares — normal equations, QR approach

Worked Examples

Common Mistakes (Steel-manned)

Recall Feynman: 12-saal ke bacche ko explain karo

Socho tum darts phenk rahe ho jo ek seedhi line par lagne chahiye, lekin tumhara haath hilta hai toh woh bikhar jaate hain. Tum ek line sab ke through nahi khich sakte. Toh tum woh line khinchte ho jो total miss-distance (upar-neeche mapa hua) ko jitna ho sake utna chota kare. "Miss" arrows line se seedhe door point karne chahiye — agar koi line ke saath lean karta, toh tum line slide kar ke better kar sakte. Least squares woh sabse fair line dhundta hai. QR sirf arithmetic karne ka ek saaf tarika hai jo tumhare calculator ki rounding errors ko nahi udaata.

Active Recall

Least squares kya minimise karta hai?

Squared residual norm

∥ b - A x ∥_{2}^{2}

Normal equations batao.

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

Geometrically, residual Col(A) se orthogonal kyun hona chahiye?

Warna uska ek component column space ke andar hoga;

A x

ko us direction mein move karne se distance kam hoti, jo minimality ke against hai.

A^{⊤} A

kab invertible hota hai?

Tab hi jab

A

ka full column rank ho (independent columns).

Col(A) par projection matrix kya hai?

P = A (A^{⊤} A)^{- 1} A^{⊤}

, with

P^{2} = P

P^{⊤} = P

A = QR

mein Q aur R ki kya properties hain?

Q

ke orthonormal columns hain (

Q^{⊤} Q = I

);

R

upper triangular aur invertible hai.

QR, least squares ko kaun si equation mein reduce karta hai?

R \hat{x} = Q^{⊤} b

, back-substitution se solve hota hai.

Normal equations se QR numerically better kyun hai?

A^{⊤} A

banane se condition number square ho jaata hai (

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

); QR isse avoid karta hai, stable rehta hai.

Norm ki jagah squared norm kyun use karte hain?

Yeh har jagah smooth/differentiable hai aur same minimiser deta hai, equations ko linear rakhta hai.

Connections

Orthogonal Projection — least squares is projection onto Col(A).
QR Factorization — solve ke peeche stable engine.
Gram-Schmidt Process — $Q$ banane ka ek tarika.
Column Space and Rank — full rank ⇔ unique solution.
Pseudoinverse (Moore-Penrose) — jab rank deficient ho tab generalise karta hai.
Condition Number — kyun $κ$ square karna nuksan karta hai.
Linear Regression — in equations ka statistics application.