Numerical Linear Algebra Cookbook

A review of numerical linear algebra for machine learning.

mathematicsdata science

This review covers material from Part 2 of Linear Algebra and Learning from Data (LALFD).

Least Squares: Solution Methods

Many applications produce overdetermined linear systems with no exact solution. Least squares finds the best approximation by minimising the error .

Setting the gradient to zero yields the normal equations:

Four computational approaches exist, ordered from most robust to regularised:

  1. Singular Value Decomposition (SVD): Compute , the pseudoinverse of , then solve . Most numerically stable for ill-conditioned matrices.
  2. Normal Equations: Solve directly when has full column rank. Fast but sensitive to numerical precision.
  3. QR Decomposition: Factor using Gram-Schmidt to produce orthogonal columns . Better numerical stability than normal equations.
  4. Regularisation: Minimise to avoid overfitting. The penalty term constrains solution magnitude, yielding .

Further Reading