Normal Equations

machine-learning linear-algebra optimisation

Definition

Normal Equations

Given a design matrix (one column per sample, one row per feature) and a target vector , the normal equations are the linear system

whose solution gives the least-squares weight vector

assuming is invertible. The bias can be absorbed into by prepending a constant to each feature vector.

Derivation

The least-squares estimator minimises the squared error on the predictions :

At the minimum the gradient vanishes:

Rearranging gives the normal equations , and inverting yields above.

Properties

Exact, single-step minimiser

The normal equations return the global minimiser of 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 , which is . The method is efficient for low-dimensional feature spaces but prohibitive when grows; iterative methods are preferred there.

Singularity

When is singular — features are collinear or — the inverse is undefined and the minimiser is not unique. A pseudoinverse or regularisation restores a unique solution.