Intuition The big pictureYou have a system A x = b A\mathbf{x} = \mathbf{b} A x = b more equations than unknowns (a tall matrix). Usually there is no exact solution — b \mathbf{b} b A A A which x ^ \hat{\mathbf{x}} x ^ A x ^ A\hat{\mathbf{x}} A x ^ b \mathbf{b} b "Closest" means smallest Euclidean distance ∥ b − A x ∥ \|\mathbf{b} - A\mathbf{x}\| ∥ b − A x ∥ projection : A x ^ A\hat{\mathbf{x}} A x ^ b \mathbf{b} b
Definition Least-squares solutionGiven A ∈ R m × n A \in \mathbb{R}^{m\times n} A ∈ R m × n m ≥ n m \ge n m ≥ n b ∈ R m \mathbf{b}\in\mathbb{R}^m b ∈ R m least-squares solution x ^ \hat{\mathbf{x}} x ^ residual norm :
x ^ = arg min x ∥ b − A x ∥ 2 2 \hat{\mathbf{x}} = \arg\min_{\mathbf{x}} \; \|\mathbf{b} - A\mathbf{x}\|_2^2 x ^ = arg min x ∥ b − A x ∥ 2 2 r = b − A x ^ \mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}} r = b − A x ^ residual .
WHY squared length? It is differentiable (smooth) everywhere, while ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥
We want the minimum of f ( x ) = ∥ b − A x ∥ 2 f(\mathbf{x}) = \|\mathbf{b} - A\mathbf{x}\|^2 f ( x ) = ∥ b − A x ∥ 2
The set { A x } \{A\mathbf{x}\} { A x } column space Col ( A ) \text{Col}(A) Col ( A ) b \mathbf{b} b orthogonal projection . So the residual must be perpendicular to every column of A A A :
a j ⊤ ( b − A x ^ ) = 0 for every column a j . \mathbf{a}_j^\top (\mathbf{b} - A\hat{\mathbf{x}}) = 0 \quad \text{for every column } \mathbf{a}_j. a j ⊤ ( b − A x ^ ) = 0 for every column a j .
Why this step? If the residual had any component lying inside Col ( A ) \text{Col}(A) Col ( A ) A x A\mathbf{x} A x zero component in the column space, i.e. it's orthogonal to all columns.
Stacking all columns gives A ⊤ ( b − A x ^ ) = 0 A^\top(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} A ⊤ ( b − A x ^ ) = 0
A ⊤ A x ^ = A ⊤ b \boxed{A^\top A\,\hat{\mathbf{x}} = A^\top \mathbf{b}} A ⊤ A x ^ = A ⊤ b
Expand:
f ( x ) = ( b − A x ) ⊤ ( b − A x ) = b ⊤ b − 2 x ⊤ A ⊤ b + x ⊤ A ⊤ A x . f(\mathbf{x}) = (\mathbf{b}-A\mathbf{x})^\top(\mathbf{b}-A\mathbf{x}) = \mathbf{b}^\top\mathbf{b} - 2\mathbf{x}^\top A^\top \mathbf{b} + \mathbf{x}^\top A^\top A \mathbf{x}. f ( x ) = ( b − A x ) ⊤ ( b − A x ) = b ⊤ b − 2 x ⊤ A ⊤ b + x ⊤ A ⊤ A x . ∇ x ( x ⊤ M x ) = 2 M x \nabla_\mathbf{x}(\mathbf{x}^\top M\mathbf{x}) = 2M\mathbf{x} ∇ x ( x ⊤ M x ) = 2 M x M = A ⊤ A M=A^\top A M = A ⊤ A ∇ x ( x ⊤ c ) = c \nabla_\mathbf{x}(\mathbf{x}^\top\mathbf{c}) = \mathbf{c} ∇ x ( x ⊤ c ) = c ∇ f = − 2 A ⊤ b + 2 A ⊤ A x = 0 ⇒ A ⊤ A x ^ = A ⊤ b . \nabla f = -2A^\top\mathbf{b} + 2A^\top A\,\mathbf{x} = \mathbf{0} \;\Rightarrow\; A^\top A\hat{\mathbf{x}} = A^\top\mathbf{b}. ∇ f = − 2 A ⊤ b + 2 A ⊤ A x = 0 ⇒ A ⊤ A x ^ = A ⊤ b . Why a minimum, not max? The Hessian 2 A ⊤ A 2A^\top A 2 A ⊤ A v ⊤ A ⊤ A v = ∥ A v ∥ 2 ≥ 0 \mathbf{v}^\top A^\top A\mathbf{v} = \|A\mathbf{v}\|^2 \ge 0 v ⊤ A ⊤ A v = ∥ A v ∥ 2 ≥ 0
WHY not just use normal equations? Forming A ⊤ A A^\top A A ⊤ A squares the condition number (κ ( A ⊤ A ) = κ ( A ) 2 \kappa(A^\top A)=\kappa(A)^2 κ ( A ⊤ A ) = κ ( A ) 2 A ⊤ A A^\top A A ⊤ A
Factor A = Q R A = QR A = QR Q Q Q orthonormal columns (Q ⊤ Q = I Q^\top Q = I Q ⊤ Q = I R R R upper triangular . Orthonormal columns are an "ideal coordinate system" — projecting is trivial, and triangular systems solve by back-substitution.
Derivation. Substitute A = Q R A=QR A = QR ( Q R ) ⊤ ( Q R ) x ^ = ( Q R ) ⊤ b ⇒ R ⊤ Q ⊤ Q ⏟ I R x ^ = R ⊤ Q ⊤ b ⇒ R ⊤ R x ^ = R ⊤ Q ⊤ b . (QR)^\top(QR)\hat{\mathbf{x}} = (QR)^\top\mathbf{b} \;\Rightarrow\; R^\top\underbrace{Q^\top Q}_{I}R\,\hat{\mathbf{x}} = R^\top Q^\top\mathbf{b} \;\Rightarrow\; R^\top R\hat{\mathbf{x}}=R^\top Q^\top\mathbf{b}. ( QR ) ⊤ ( QR ) x ^ = ( QR ) ⊤ b ⇒ R ⊤ I Q ⊤ Q R x ^ = R ⊤ Q ⊤ b ⇒ R ⊤ R x ^ = R ⊤ Q ⊤ b . R R R R ⊤ R^\top R ⊤
R x ^ = Q ⊤ b \boxed{R\,\hat{\mathbf{x}} = Q^\top\mathbf{b}} R x ^ = Q ⊤ b
Why this step? R R R back-substitution — fast and numerically stable. No A ⊤ A A^\top A A ⊤ A
Worked example Example 1 — Best-fit line via normal equationsFit y = c + d t y = c + d\,t y = c + d t ( 0 , 6 ) , ( 1 , 0 ) , ( 2 , 0 ) (0,6),(1,0),(2,0) ( 0 , 6 ) , ( 1 , 0 ) , ( 2 , 0 ) Set up A x = b A\mathbf{x}=\mathbf{b} A x = b x = ( c , d ) ⊤ \mathbf{x}=(c,d)^\top x = ( c , d ) ⊤ A = ( 1 0 1 1 1 2 ) , b = ( 6 0 0 ) A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix},\quad \mathbf{b}=\begin{pmatrix}6\\0\\0\end{pmatrix} A = 1 1 1 0 1 2 , b = 6 0 0 Why? Each row is "predict y i y_i y i c + d t i c+d t_i c + d t i
Compute A ⊤ A = ( 3 3 3 5 ) A^\top A=\begin{pmatrix}3&3\\3&5\end{pmatrix} A ⊤ A = ( 3 3 3 5 ) A ⊤ b = ( 6 0 ) A^\top\mathbf{b}=\begin{pmatrix}6\\0\end{pmatrix} A ⊤ b = ( 6 0 ) Why? A ⊤ A A^\top A A ⊤ A 1 ⋅ 1 = 3 \mathbf{1}\cdot\mathbf{1}=3 1 ⋅ 1 = 3 1 ⋅ t = 3 \mathbf{1}\cdot\mathbf{t}=3 1 ⋅ t = 3 t ⋅ t = 5 \mathbf{t}\cdot\mathbf{t}=5 t ⋅ t = 5
Solve ( 3 3 3 5 ) ( c d ) = ( 6 0 ) \begin{pmatrix}3&3\\3&5\end{pmatrix}\binom{c}{d}=\binom{6}{0} ( 3 3 3 5 ) ( d c ) = ( 0 6 ) 2 d = − 6 ⇒ d = − 3 2d=-6\Rightarrow d=-3 2 d = − 6 ⇒ d = − 3 3 c − 9 = 6 ⇒ c = 5 3c-9=6\Rightarrow c=5 3 c − 9 = 6 ⇒ c = 5 Best line: y = 5 − 3 t y = 5 - 3t y = 5 − 3 t ( 5 , 2 , − 1 ) (5,2,-1) ( 5 , 2 , − 1 ) ( 1 , − 2 , 1 ) (1,-2,1) ( 1 , − 2 , 1 ) A ⊤ r = 0 A^\top\mathbf{r}=0 A ⊤ r = 0
Worked example Example 2 — Same problem via QRColumns of A A A a 1 = ( 1 , 1 , 1 ) \mathbf{a}_1=(1,1,1) a 1 = ( 1 , 1 , 1 ) a 2 = ( 0 , 1 , 2 ) \mathbf{a}_2=(0,1,2) a 2 = ( 0 , 1 , 2 )
q 1 = a 1 / ∥ a 1 ∥ = 1 3 ( 1 , 1 , 1 ) \mathbf{q}_1 = \mathbf{a}_1/\|\mathbf{a}_1\| = \tfrac{1}{\sqrt3}(1,1,1) q 1 = a 1 /∥ a 1 ∥ = 3 1 ( 1 , 1 , 1 ) Remove projection: a 2 − ( q 1 ⊤ a 2 ) q 1 \mathbf{a}_2 - (\mathbf{q}_1^\top\mathbf{a}_2)\mathbf{q}_1 a 2 − ( q 1 ⊤ a 2 ) q 1 q 1 ⊤ a 2 = 3 / 3 = 3 \mathbf{q}_1^\top\mathbf{a}_2 = 3/\sqrt3=\sqrt3 q 1 ⊤ a 2 = 3/ 3 = 3 3 ⋅ 1 3 ( 1 , 1 , 1 ) = ( 1 , 1 , 1 ) \sqrt3\cdot\tfrac1{\sqrt3}(1,1,1)=(1,1,1) 3 ⋅ 3 1 ( 1 , 1 , 1 ) = ( 1 , 1 , 1 ) ( − 1 , 0 , 1 ) (-1,0,1) ( − 1 , 0 , 1 ) q 2 = 1 2 ( − 1 , 0 , 1 ) \mathbf{q}_2=\tfrac1{\sqrt2}(-1,0,1) q 2 = 2 1 ( − 1 , 0 , 1 )
Then R = Q ⊤ A = ( 3 3 0 2 ) R=Q^\top A=\begin{pmatrix}\sqrt3 & \sqrt3\\0 & \sqrt2\end{pmatrix} R = Q ⊤ A = ( 3 0 3 2 ) Q ⊤ b = ( 6 / 3 − 6 / 2 ) Q^\top\mathbf{b}=\begin{pmatrix}6/\sqrt3\\-6/\sqrt2\end{pmatrix} Q ⊤ b = ( 6/ 3 − 6/ 2 ) R x ^ = Q ⊤ b R\hat{\mathbf{x}}=Q^\top\mathbf{b} R x ^ = Q ⊤ b 2 d = − 6 / 2 ⇒ d = − 3 \sqrt2\,d=-6/\sqrt2\Rightarrow d=-3 2 d = − 6/ 2 ⇒ d = − 3 3 c + 3 ( − 3 ) = 6 / 3 = 2 3 ⇒ c = 5 \sqrt3 c+\sqrt3(-3)=6/\sqrt3=2\sqrt3\Rightarrow c=5 3 c + 3 ( − 3 ) = 6/ 3 = 2 3 ⇒ c = 5 Same answer , no squaring. ✓
Common mistake "Just invertA A A x = A − 1 b \mathbf{x}=A^{-1}\mathbf{b} x = A − 1 b Why it feels right: that's how square systems work. Fix: A A A m × n m\times n m × n A ⊤ A x ^ = A ⊤ b A^\top A\hat{\mathbf{x}}=A^\top\mathbf{b} A ⊤ A x ^ = A ⊤ b
A ⊤ A A^\top A A ⊤ A Why it feels right: it's square and symmetric. Fix: it's invertible iff A A A x ^ \hat{\mathbf{x}} x ^
Common mistake "Normal equations and QR give different answers."Why it feels right: the formulas look unrelated. Fix: R x ^ = Q ⊤ b R\hat{\mathbf{x}}=Q^\top\mathbf{b} R x ^ = Q ⊤ b algebraically the same equation; QR is just a numerically safer route to the identical x ^ \hat{\mathbf{x}} x ^
Common mistake "The residual is part of the fit, so make it lie inCol ( A ) \text{Col}(A) Col ( A ) Why it feels right: everything seems to come from A A A Fix: the residual must be orthogonal to Col ( A ) \text{Col}(A) Col ( A )
Recall Feynman: explain to a 12-year-oldImagine throwing darts that should all hit one straight line, but your hand wobbles so they scatter. You can't draw a line through all of them. So you draw the line that makes the total miss-distance (measured up-and-down) as small as possible. The "miss" arrows must point straight away from the line — if any leaned along the line, you could slide the line and do better. Least squares finds that fairest line. QR is just a tidier way to do the arithmetic that doesn't blow up your calculator's rounding errors.
Mnemonic Remember the formula"A-Transpose-A times x-hat equals A-Transpose-b" → say "AT-A, AT-b" like a drumbeat. For QR: "R x equals Q-transpose b" — "Are eXes Quite Tidy? b!" (Rx = Qᵀb).
What does least squares minimise? The squared residual norm
∥ b − A x ∥ 2 2 \|\mathbf{b}-A\mathbf{x}\|_2^2 ∥ b − A x ∥ 2 2 .
State the normal equations. A ⊤ A x ^ = A ⊤ b A^\top A\hat{\mathbf{x}} = A^\top\mathbf{b} A ⊤ A x ^ = A ⊤ b .
Geometrically, why must the residual be orthogonal to Col(A)? Otherwise it has a component inside the column space; moving
A x A\mathbf{x} A x along it would reduce the distance, contradicting minimality.
When is A ⊤ A A^\top A A ⊤ A Exactly when
A A A has full column rank (independent columns).
What is the projection matrix onto Col(A)? P = A ( A ⊤ A ) − 1 A ⊤ P = A(A^\top A)^{-1}A^\top P = A ( A ⊤ A ) − 1 A ⊤ , with
P 2 = P P^2=P P 2 = P ,
P ⊤ = P P^\top=P P ⊤ = P .
In A = Q R A=QR A = QR Q Q Q has orthonormal columns (
Q ⊤ Q = I Q^\top Q=I Q ⊤ Q = I );
R R R is upper triangular and invertible.
What equation does QR reduce least squares to? R x ^ = Q ⊤ b R\hat{\mathbf{x}} = Q^\top\mathbf{b} R x ^ = Q ⊤ b , solved by back-substitution.
Why prefer QR over normal equations numerically? Forming
A ⊤ A A^\top A A ⊤ A squares the condition number (
κ ( A ⊤ A ) = κ ( A ) 2 \kappa(A^\top A)=\kappa(A)^2 κ ( A ⊤ A ) = κ ( A ) 2 ); QR avoids it, staying stable.
Why use the squared norm rather than the norm itself? It's smooth/differentiable everywhere and gives the same minimiser, keeping the equations linear.
Orthogonal Projection — least squares is projection onto Col(A).QR Factorization — the stable engine behind the solve.Gram-Schmidt Process — one way to build Q Q Q Column Space and Rank — full rank ⇔ unique solution.Pseudoinverse (Moore-Penrose) — generalises when rank is deficient.Condition Number — why squaring κ \kappa κ Linear Regression — statistics application of these equations.
residual orthogonal to Col A
Tall system Ax=b, no exact solution
Least-squares solution x-hat
Normal equations A^T A x = A^T b
x-hat = A^T A inverse times A^T b
Projection A x-hat onto Col A
Intuition Hinglish mein samjhoDekho, problem ye hai: tumhare paas A x = b A\mathbf{x}=\mathbf{b} A x = b b \mathbf{b} b x ^ \hat{\mathbf{x}} x ^ A x ^ A\hat{\mathbf{x}} A x ^ b \mathbf{b} b projection hai: A x ^ A\hat{\mathbf{x}} A x ^ b \mathbf{b} b
Key insight: jo bachi hui galti (residual b − A x ^ \mathbf{b}-A\hat{\mathbf{x}} b − A x ^ perpendicular honi chahiye. Agar woh thodi bhi plane ke andar lean kare, toh hum line ko adjust karke aur paas ja sakte the — matlab minimum nahi tha. Is orthogonality se seedha nikalta hai normal equation : A ⊤ A x ^ = A ⊤ b A^\top A\hat{\mathbf{x}}=A^\top\mathbf{b} A ⊤ A x ^ = A ⊤ b
QR approach kyun? Jab tum A ⊤ A A^\top A A ⊤ A A = Q R A=QR A = QR Q Q Q R R R R x ^ = Q ⊤ b R\hat{\mathbf{x}}=Q^\top\mathbf{b} R x ^ = Q ⊤ b
Practical baat: ye exactly linear regression ka maths hai — best-fit line/curve nikaalna. Toh jab bhi tum data par line fit karoge, andar yahi normal equations ya QR chal raha hota hai. Full column rank hona zaroori hai warna A ⊤ A A^\top A A ⊤ A
