OLS: The Normal EquationOpen in Colab

OLS: The Normal Equation

Ordinary Least Squares (OLS) minimizes the sum of squared residuals ∥y−Xw∥2\|\mathbf{y} - X\mathbf{w}\|^2 and has an exact closed-form solution. This page derives that solution step by step and verifies it on a concrete 3-point example.

The OLS objective

We want the weight vector w\mathbf{w} that minimizes:

L(w)=∥y−Xw∥2=(y−Xw)⊤(y−Xw)\mathcal{L}(\mathbf{w}) = \|\mathbf{y} - X\mathbf{w}\|^2 = (\mathbf{y} - X\mathbf{w})^\top(\mathbf{y} - X\mathbf{w})

The 1n\frac{1}{n} scaling constant is dropped — it doesn't affect where the minimum is.

Deriving the normal-equation solution

Step 1: Expand the squared norm. Use (a−b)⊤(a−b)=a⊤a−2a⊤b+b⊤b(\mathbf{a}-\mathbf{b})^\top(\mathbf{a}-\mathbf{b}) = \mathbf{a}^\top\mathbf{a} - 2\mathbf{a}^\top\mathbf{b} + \mathbf{b}^\top\mathbf{b} (valid because y⊤Xw\mathbf{y}^\top X\mathbf{w} is a scalar, equal to its transpose w⊤X⊤y\mathbf{w}^\top X^\top\mathbf{y}):

L(w)=y⊤y−2 w⊤X⊤y+w⊤X⊤X w\mathcal{L}(\mathbf{w}) = \mathbf{y}^\top\mathbf{y} - 2\,\mathbf{w}^\top X^\top\mathbf{y} + \mathbf{w}^\top X^\top X\,\mathbf{w}

Step 2: Take the gradient with respect to w\mathbf{w}. Two standard matrix-calculus identities:

∇w(w⊤b)=b,∇w(w⊤Aw)=2Aw(A symmetric)\nabla_{\mathbf{w}}(\mathbf{w}^\top\mathbf{b}) = \mathbf{b}, \qquad \nabla_{\mathbf{w}}(\mathbf{w}^\top A\mathbf{w}) = 2A\mathbf{w} \quad (A \text{ symmetric})

A=X⊤XA = X^\top X is symmetric. The first term y⊤y\mathbf{y}^\top\mathbf{y} has no w\mathbf{w}, so its gradient is 0\mathbf{0}:

∇wL=−2X⊤y+2X⊤X w\nabla_{\mathbf{w}}\mathcal{L} = -2X^\top\mathbf{y} + 2X^\top X\,\mathbf{w}

Step 3: Set the gradient to zero. This is the normal equation:

−2X⊤y+2X⊤X w=0⟹X⊤X w=X⊤y-2X^\top\mathbf{y} + 2X^\top X\,\mathbf{w} = \mathbf{0} \quad\Longrightarrow\quad X^\top X\,\mathbf{w} = X^\top\mathbf{y}

Step 4: Solve for w\mathbf{w}. Left-multiply both sides by (X⊤X)−1(X^\top X)^{-1}:

  w∗=(X⊤X)−1X⊤y  \boxed{\;\mathbf{w}^* = (X^\top X)^{-1}X^\top\mathbf{y}\;}

This is a global minimum (not a saddle point) because the Hessian ∇w2L=2X⊤X\nabla^2_{\mathbf{w}}\mathcal{L} = 2X^\top X is positive semi-definite — the loss is convex.

When does (XᵀX)⁻¹ exist?

X⊤XX^\top X is invertible if and only if the columns of XX are linearly independent — no feature is a linear combination of the others (no perfect collinearity) and n≥dn \geq d (not more features than samples). When this fails, use Ridge regression: (X⊤X+λI)(X^\top X + \lambda I) is always invertible for λ>0\lambda > 0.

A hand-worked 3-point example

Data: (x,y)=(1,2), (2,3), (3,5)(x, y) = (1, 2),\,(2, 3),\,(3, 5). Fit y^=w0+w1x\hat{y} = w_0 + w_1 x.

Add a leading ones column for the bias w0w_0:

X=[111213],y=[235]X = \begin{bmatrix}1 & 1\\1 & 2\\1 & 3\end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix}2\\3\\5\end{bmatrix}

Compute X⊤XX^\top X (a 2×22\times 2 matrix):

X⊤X=[1+1+11+2+31+2+31+4+9]=[36614]X^\top X = \begin{bmatrix}1+1+1 & 1+2+3\\1+2+3 & 1+4+9\end{bmatrix} = \begin{bmatrix}3 & 6\\6 & 14\end{bmatrix}

Compute X⊤yX^\top\mathbf{y}:

X⊤y=[2+3+51⋅2+2⋅3+3⋅5]=[1023]X^\top\mathbf{y} = \begin{bmatrix}2+3+5\\1\cdot2+2\cdot3+3\cdot5\end{bmatrix} = \begin{bmatrix}10\\23\end{bmatrix}

Invert X⊤XX^\top X. For [abcd]−1=1ad−bc[d−b−ca]\begin{bmatrix}a&b\\c&d\end{bmatrix}^{-1} = \frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}. Determinant =3⋅14−62=42−36=6= 3\cdot14 - 6^2 = 42 - 36 = 6:

(X⊤X)−1=16[14−6−63](X^\top X)^{-1} = \frac{1}{6}\begin{bmatrix}14 & -6\\-6 & 3\end{bmatrix}

Multiply (X⊤X)−1X⊤y(X^\top X)^{-1}X^\top\mathbf{y}:

w∗=16[14−6−63][1023]=16[140−138−60+69]=16[29]=[0.3331.5]\mathbf{w}^* = \frac{1}{6}\begin{bmatrix}14 & -6\\-6 & 3\end{bmatrix}\begin{bmatrix}10\\23\end{bmatrix} = \frac{1}{6}\begin{bmatrix}140-138\\-60+69\end{bmatrix} = \frac{1}{6}\begin{bmatrix}2\\9\end{bmatrix} = \begin{bmatrix}0.333\\1.5\end{bmatrix}

Fitted line: y^=0.333+1.5 x\hat{y} = 0.333 + 1.5\,x.

Verify: predictions y^1=1.833\hat{y}_1 = 1.833, y^2=3.333\hat{y}_2 = 3.333, y^3=4.833\hat{y}_3 = 4.833; residuals 0.167,−0.333,0.1670.167, -0.333, 0.167; SSres=0.167SS_{\text{res}} = 0.167; SStot=4.667SS_{\text{tot}} = 4.667; R2=0.964R^2 = 0.964. Prediction at x=4x=4: y^=6.333\hat{y} = 6.333.

The same computation in NumPy

Python
import numpy as np

X = np.array([[1, 1], [1, 2], [1, 3]], dtype=float)  # bias column prepended
y = np.array([2.0, 3.0, 5.0])

# Normal equation: w = (X^T X)^{-1} X^T y
w = np.linalg.solve(X.T @ X, X.T @ y)   # solve is more stable than explicit inversion
print("w:", w.round(3))                   # [0.333, 1.5]

# Or with lstsq (handles rank-deficient X):
w2, _, _, _ = np.linalg.lstsq(X, y, rcond=None)
print("lstsq:", w2.round(3))              # same result

# Predictions and R²
y_hat = X @ w
ss_res = np.sum((y - y_hat)**2)
ss_tot = np.sum((y - y.mean())**2)
print(f"R² = {1 - ss_res/ss_tot:.3f}")   # 0.964

Related concepts

  • Linear Regression: source lesson with the full model, Ridge, Lasso
  • Ridge Regression: adds λI\lambda I to make X⊤X+λIX^\top X + \lambda I always invertible
  • Gradient Descent: the iterative alternative when dd is too large for direct inversion

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
OLS: The Normal EquationMLE for the GaussianRidge & Lasso Regularizat…Linear RegressionRegularization: Ridge & L…Gradient Descent