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 Ax=b with no exact solution. Least squares finds the best approximation \hat{x} by minimising the error \lvert \lvert b - A \hat{x} \rvert \rvert^2.

Setting the gradient to zero yields the normal equations: A^T A \hat{x} = A^T b

Four computational approaches exist. The first three are ordered from most to least numerically robust; the fourth changes the problem itself:

  1. Singular Value Decomposition (SVD): Compute A^+, the pseudoinverse of A, then solve \hat{x}=A^+b. Most numerically stable for ill-conditioned matrices.

  2. QR Decomposition: Factor A=QR to produce orthogonal columns Q, then solve R\hat{x} = Q^Tb. Much more stable than the normal equations, provided the factorisation is computed with Householder reflections or modified Gram-Schmidt; classical Gram-Schmidt loses orthogonality in floating point.

  3. Normal Equations: Solve A^TA\hat{x} = A^Tb directly when A has full column rank. Fast but sensitive to numerical precision, since forming A^TA squares the condition number.

  4. Regularisation: To avoid overfitting, minimise

    \lvert \lvert b - A \hat{x} \rvert \rvert^2 + \delta^2 \lvert \lvert x \rvert \rvert^2

    The penalty term constrains solution magnitude, yielding (A^TA + \delta^2 I)x_{\delta} = A^T b.

Further Reading