Normal Equations

machine-learning linear-algebra optimisation

Definition

Normal Equations

The normal equations provide a closed-form analytical solution for finding the optimal parameters $\mathbf{w}$ that minimise the sum of squared errors in a linear regression task. Formally, given a design matrix $X$ and a target vector $\mathbf{y}$, the optimal weight vector ${\mathbf{w}}^{\ast }$ is:

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

where $X\in {\mathbb{R}}^{D\times m}$ is the matrix of input features (with $m$ samples as columns) and $\mathbf{y}\in {\mathbb{R}}^m$ is the target vector.

Operational Properties

Exact Minimisation: Unlike iterative methods like gradient descent, the normal equations provide the global minimum of the quadratic loss function in a single computational step, requiring no hyperparameters such as a learning rate.

Computational Complexity: The solution requires the inversion of the matrix $X{X}^{\top }\in {\mathbb{R}}^{D\times D}$, which has a complexity of $O(D^3)$. This makes the method highly efficient for low-dimensional feature spaces but computationally prohibitive as the number of features $D$ increases.