Normal Equations

machine-learning linear-algebra optimisation

Definition

Normal Equations

Given a design matrix $X\in {\mathbb{R}}^{D\times m}$ (one column per sample, one row per feature) and a target vector $\mathbf{y}\in {\mathbb{R}}^m$, the normal equations are the linear system

$$X{X}^{\top }\mathbf{w}=X\mathbf{y},$$

whose solution gives the least-squares weight vector

$${\mathbf{w}}^{\ast }=(X{X}^{\top }{)}^{-1}X\mathbf{y},$$

assuming $X{X}^{\top }$ is invertible. The bias can be absorbed into $\mathbf{w}$ by prepending a constant $1$ to each feature vector.

Derivation

The least-squares estimator minimises the squared error on the predictions $X^{\top }\mathbf{w}$:

$$J(\mathbf{w})=\Vert X^{\top }\mathbf{w}-\mathbf{y}{\Vert }^2.$$

At the minimum the gradient vanishes:

$${\nabla }_{\mathbf{w}}J(\mathbf{w})=2X(X^{\top }\mathbf{w}-\mathbf{y})=0.$$

Rearranging gives the normal equations $X{X}^{\top }\mathbf{w}=X\mathbf{y}$, and inverting $X{X}^{\top }$ yields ${\mathbf{w}}^{\ast }$ above.

Properties

Exact, single-step minimiser

The normal equations return the global minimiser of $J$ in one solve, with no learning rate and no iteration. This contrasts with gradient descent, which approaches the same minimiser asymptotically.

Cubic cost in the feature dimension

The dominant cost is inverting $X{X}^{\top }\in {\mathbb{R}}^{D\times D}$, which is $O(D^3)$. The method is efficient for low-dimensional feature spaces but prohibitive when $D$ grows; iterative methods are preferred there.

Singularity

When $X{X}^{\top }$ is singular — features are collinear or $D>m$ — the inverse is undefined and the minimiser is not unique. A pseudoinverse or regularisation restores a unique solution.