Ordinary Least Squares (OLS) & Normal Equation Derivations
“Minimizing Residual Sum of Squares (RSS), matrix calculus derivations, and projection onto the column space.”
1.The Linear Regression Formulation & Matrix Calculus
§ 1.1.In linear regression, we model the relationship between an n x d feature matrix X and an n x 1 target vector y as: y = Xw + epsilon, where epsilon is an unobserved noise vector with mean zero and variance sigma^2 I.
Derivation of the Normal Equations:
1. Express the objective function as the quadratic scalar form: L(w) = (y - Xw)^T (y - Xw) = y^T y - 2 w^T X^T y + w^T X^T X w.
2. Take the vector derivative with respect to w using standard matrix identities (d(a^T w)/dw = a and d(w^T A w)/dw = 2 A w for symmetric A):
grad_w L(w) = - 2 X^T y + 2 X^T X w.
3. Set the gradient to zero to find the stationary point: 2 X^T X w = 2 X^T y => (X^T X) w = X^T y.
4. When X has full column rank, X^T X is positive definite and invertible: w* = (X^T X)^{-1} X^T y.
The residual vector e = y - y_hat is strictly orthogonal to every column vector in X. Mathematically: X^T e = X^T (y - Xw*) = X^T y - X^T X (X^T X)^{-1} X^T y = 0. This is a recurring conceptual trap in GATE DA questions.
2. Worked Practice Problem: 2D Feature Normal Equation Calculation
Remember to prepend a column of 1s to account for the intercept term w0.
Problem: Fit a line y = w0 + w1 * x through data points (1, 2), (2, 5), (3, 7) using Ordinary Least Squares.
Step 1: Construct design matrix X and target y:
X = [ 1 1 ]
[ 1 2 ]
[ 1 3 ]
y = [ 2, 5, 7 ]^T
Step 2: Compute X^T X:
X^T X = [ 1 1 1 ] [ 1 1 ] = [ 3 6 ]
[ 1 2 3 ] [ 1 2 ] [ 6 14 ]
[ 1 3 ]
Step 3: Compute X^T y:
X^T y = [ 1 1 1 ] [ 2 ] = [ 14 ]
[ 1 2 3 ] [ 5 ] [ 33 ]
[ 7 ]
Step 4: Invert (X^T X):
Det(X^T X) = (3)(14) - (6)(6) = 42 - 36 = 6.
(X^T X)^{-1} = (1/6) * [ 14 -6 ] = [ 7/3 -1 ]
[ -6 3 ] [ -1 1/2 ]
Step 5: Multiply (X^T X)^{-1} * X^T y:
w0 = (7/3)(14) + (-1)(33) = 98/3 - 99/3 = -1/3 ≈ -0.333
w1 = (-1)(14) + (1/2)(33) = -14 + 16.5 = 2.5 = 5/2
Final Model: y_hat = -0.333 + 2.5 * x.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.