Least squares — normal equations, QR approach: Question bank

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

Shuru karne se pehle, ye vocabulary tumhare paas honi chahiye (sab parent note mein build hoti hai): residual $r = b - A \hat{x}$ (yani "miss" vector), column space $Col (A)$ (saare reachable outputs $A x$ ), aur projection $\hat{b} = A \hat{x}$ ( $b$ ki us subspace par shadow). Agar inme se koi shaky lage toh Orthogonal Projection aur Column Space and Rank dekho.

True or false — justify karo

Har claim ya toh true hai ya false. Batao kaun sa hai, phir ek-sentence ka reason do — wahi reason poora point hai.

Least-squares solution hamesha

A \hat{x} = b

exactly banata hai.

False — ye

A \hat{x}

Col (A)

mein

b

ka sabse kareeb point banata hai; equality sirf tab hoti hai jab

b

pehle se column space mein ho.

Agar

b

Col (A)

mein lie karta hai, toh residual zero vector hota hai.

True — tab

b

reachable hai, projection exactly

b

par land karta hai, aur

r = b - \hat{b} = 0

; least squares exact solution recover kar leta hai.

∥ b - A x ∥

minimise karna aur

∥ b - A x ∥^{2}

minimise karna dono ek hi

\hat{x}

dete hain.

True — square karna ek non-negative length ka strictly increasing function hai, isliye minimum ki location preserve hoti hai jabki objective smooth aur differentiable ban jaati hai.

Projection matrix

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

invertible hai.

False —

P

har us cheez ko zero kar deta hai jo

Col (A)

ke orthogonal hai, isliye ye singular hai (jab tak

Col (A)

poora

R^{m}

na ho); ye

P^{2} = P

satisfy karta hai, jo ek invertible matrix ke liye

P = I

force karega.

Tall full-rank

A

ke liye, normal equations

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

ka hamesha exactly ek solution hota hai.

True — full column rank

A^{⊤} A

ko invertible banata hai, isliye

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

unique hai.

Residual

r

b

ke orthogonal hota hai.

False —

r

Col (A)

ke orthogonal hai (isliye

\hat{b}

ke bhi),

b

ke nahi;

b = \hat{b} + r

ek right triangle ka leg-plus-leg hai, isliye

r \cdot b = r \cdot r = ∥ r ∥^{2} \neq = 0

generally.

QR factorization aur normal equations genuinely alag answers

\hat{x}

de sakte hain.

False —

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

algebraically normal equations ke identical hai; ye sirf floating-point roundoff mein differ karte hain, aur QR zyada accurate route hai. Dekho QR Factorization.

A^{⊤} A

har matrix

A

ke liye symmetric hai.

True —

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

; symmetry ke liye

A

par koi assumption nahi chahiye, jabki invertibility ke liye full column rank chahiye.

Error dhundho

Har line mein ek plausible-sounding claim ya "solution step" hai. Flaw dhundho aur correct version batao.

"Kyunki

A x = b

ka koi solution nahi, bas

x = A^{- 1} b

compute kar lo."

A

m \times n

matrix hai jahan

m > n

, isliye ye non-square hai aur iska koi inverse nahi; pehle project karna hoga, jo deta hai

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

A^{⊤} A

square aur symmetric hai, isliye ye invertible hai."

Square aur symmetric hona invertible hona imply nahi karta —

A^{⊤} A

invertible hai iff

A

ke independent columns hain (full column rank); dependent columns ise singular bana dete hain. Dekho Column Space and Rank.

"Best fit residual ko

Col (A)

ke andar rakhta hai taaki data ke saath consistent ho."

Bilkul ulta hai — residual

Col (A)

ke orthogonal hona chahiye; column space ke andar koi bhi component

A x

ko move karke cancel ho sakta tha, isliye minimising residual ka in-space component zero hota hai.

"Humne

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

solve kiya lekin

R^{⊤}

cancel nahi kar sake, isliye QR fail ho gaya."

R

upper triangular aur invertible (full rank) hai, isliye

R^{⊤}

bhi invertible hai, toh hum legitimately ise cancel karke

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

paate hain; QR fail nahi hota.

A^{⊤} A

form karna numerically theek hai kyunki ye ek chhoti square matrix hai."

Size issue nahi hai —

A^{⊤} A

form karna condition number ko square kar deta hai (

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

), roundoff ko amplify karta hai; QR kabhi ise form nahi karta. Dekho Condition Number.

Q

orthonormal hai, isliye

Q

ek square orthogonal matrix hai aur

Q Q^{⊤} = I

Tall matrix ke thin QR mein,

Q

m \times n

matrix hai jiske columns orthonormal hain, isliye

Q^{⊤} Q = I_{n}

lekin

Q Q^{⊤} = P \neq = I

(ye identity nahi,

Col (A)

par projection hai).

"Projection

\hat{b}

hamesha

b

se chhhota hota hai, isliye

∥ \hat{b} ∥ < ∥ b ∥

strictly."

Pythagoras se

∥ b ∥^{2} = ∥ \hat{b} ∥^{2} + ∥ r ∥^{2}

, isliye

∥ \hat{b} ∥ \leq ∥ b ∥

equality ke saath jab

r = 0

ho (yani

b \in Col (A)

); ye hamesha strict nahi hota.

Why questions

Sirf fact nahi, reason do — yahan asli samajh rehti hai.

Hum residual length ko square kyun karte hain instead of length directly minimise karne ke?

Plain length

∥ \cdot ∥

zero par non-differentiable kink rakhta hai, jabki square har jagah smooth hai; squaring wahi minimiser rakhta hai lekin calculus ko (gradient zero set karo) clean linear normal equations produce karne deta hai.

Residual

A

ke har column ke orthogonal kyun hona chahiye, sirf

b

ke nahi?

Columns

Col (A)

ko span karte hain; unme se sabke orthogonal hona matlab poore subspace ke orthogonal hona hai, jo precisely wahi condition hai ki

A x

ki koi small move distance nahi ghata sakti.

f (x) = ∥ b - A x ∥^{2}

ka critical point minimum kyun hai, maximum ya saddle kyun nahi?

Hessian

2 A^{⊤} A

hai, aur

v^{⊤} A^{⊤} A v = ∥ A v ∥^{2} \geq 0

, isliye Hessian positive semidefinite hai — surface har direction mein upar curve karti hai, jo minimum force karta hai.

QR least-squares solve ko back-substitution mein kyun convert kar deta hai?

A = QR

substitute karne aur

Q^{⊤} Q = I

use karne se problem

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

par reduce ho jaati hai, aur

R

upper triangular hone ka matlab hai ki har unknown simple back-substitution se bottom row se upar milta hai — fast aur stable.

Projection matrix

P^{2} = P

kyun satisfy karta hai?

Col (A)

ke andar pehle se maujood vector ko project karna use unchanged chhod deta hai, isliye

P

do baar apply karna ek baar jitna hi hai; algebraically

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

Gram–Schmidt ka "subtract the projection" step orthogonal columns kyun produce karta hai?

a_{2}

q_{1}

along wala component remove karne se exactly woh part bachta hai jo

q_{1}

ke perpendicular hai, isliye naye vector ka

q_{1}

ke saath dot product construction se zero hota hai. Dekho Gram-Schmidt Process.

Scattered data par line fit karne ke liye least squares natural tool kyun hai?

Data ka kisi bhi line par exactly lie karna rare hai (overdetermined system), isliye hum woh line dhundhte hain jiska total squared vertical miss sabse kam ho — precisely

b

ka two-column model space par least-squares projection. Dekho Linear Regression.

Edge cases

Wo scenarios jo naive picture bhool jaati hai — degenerate rank, non-uniqueness, aur boundaries.

Agar

A

ke dependent columns hain, toh

\hat{x}

ka kya hoga?

A^{⊤} A

singular hai, isliye

\hat{x}

non-unique hai — solutions ki poori family hai jo sab ek hi projection

\hat{b}

deti hain; Pseudoinverse (Moore-Penrose) unique minimum-norm wala choose karta hai.

Jab

\hat{x}

non-unique ho, tab bhi kya projection

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

unique hoti hai?

Haan — kisi subspace mein sabse kareeb point hamesha unique hota hai; sirf coordinates

\hat{x}

ambiguous ho jaate hain jab columns dependent hों.

Jab

b = 0

ho toh least-squares solution kya hoga?

A^{⊤} b = 0

, isliye

\hat{x} = 0

(full rank ke liye) aur residual

0

hai — kisi bhi subspace mein origin ka sabse kareeb point origin hi hota hai.

Agar

m = n

aur

A

invertible ho (square consistent system) toh kya hoga?

Least squares ordinary solve mein degenerate ho jaata hai: residual exactly zero hai,

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

reduce ho jaata hai

\hat{x} = A^{- 1} b

par, aur full space

Col (A) = R^{n}

par projection identity hai.

Agar

b

A

ke sab columns ke orthogonal ho toh kya hoga?

Tab

A^{⊤} b = 0

, jo deta hai

\hat{x} = 0

, projection

\hat{b} = 0

, aur residual

r = b

— best fit zero vector hai kyunki

b

poori tarah model space ke bahar point karta hai.

Agar do data points ka

t

same ho lekin

y

alag ho, toh kya ek line dono ko exactly fit kar sakti hai?

Nahi — ek function ek

t

par ek hi

y

deta hai, isliye system inconsistent hai; least squares un dono ki average height se line fit karta hai, aur us

t

par residuals gap ko split karte hain.

Horizontal-line fit (ones ka single constant column) ke liye, least squares kya compute karta hai?

1

ke span par projection data ka mean hai — constant model ka least squares literally average return karta hai, woh point jo total squared deviation minimise karta hai. Dekho Linear Regression.

Kya ek extra data point add karna kabhi minimum residual norm badha sakta hai?

Haan — ek naya point generally usi low-dimensional model se perfectly fit nahi ho sakta, isliye total squared miss sirf equal reh sakta hai ya badh sakta hai; zyada constraints overdetermined fit ko kabhi aasaan nahi banate.

Recall Traps ka one-line summary

Least squares = project karo, invert mat karo; residual column space ke orthogonal hai (andar nahi); $A^{⊤} A$ invertible hai sirf full column rank ke saath; aur QR normal equations jaisa same answer deta hai lekin numerically safer raaste se.