Mastering Least Squares and Matrix Methods in Undergraduate Mathematics

In undergraduate mathematics, you will frequently encounter systems of linear equations that are overdetermined, meaning there are more equations than unknowns. In such cases, an exact solution rarely exists. The method of least squares provides the best possible approximate solution by minimising the sum of the squares of the residuals.

Understanding this technique is essential for your success in linear algebra and statistics modules. By mastering matrix methods, you move beyond simple curve fitting and gain the ability to solve complex regression problems analytically. This article will guide you through the derivation of the normal equations and demonstrate how to apply them using matrix algebra.

The Geometry of Overdetermined Systems

Consider a system of linear equations represented by $Ax = b$, where $A$ is an $m \times n$ matrix, $x$ is an $n \times 1$ vector of unknowns, and $b$ is an $m \times 1$ vector of observations. When $m > n$, the system is overdetermined. Geometrically, the vector $b$ likely lies outside the column space of $A$.

We seek a vector $\hat{x}$ such that $A\hat{x}$ is the orthogonal projection of $b$ onto the column space of $A$. This minimises the residual vector $r = b - A\hat{x}$. The error is minimised when the residual is orthogonal to the column space of $A$, leading to the condition $A^T(b - A\hat{x}) = 0$.

Deriving the Normal Equations

The condition $A^T(b - A\hat{x}) = 0$ can be rearranged into the famous normal equations:

$$A^T A \hat{x} = A^T b$$

This system of equations provides the closed-form solution for the least squares estimator. If $A$ has full column rank, $A^T A$ is invertible, and the unique solution is given by:

$$\hat{x} = (A^T A)^{-1} A^T b$$

This matrix method is computationally efficient for small to medium-sized datasets and avoids the iterative nature of gradient descent.

Worked Example 1: Simple Linear Regression

Suppose we have data points $(1, 2), (2, 3), (3, 5)$. We want to fit a line $y = \alpha + \beta x$.

1. Set up the system $Ax = b$: $$A = \begin{pmatrix} 1 & 1 \ 1 & 2 \ 1 & 3 \end{pmatrix}, x = \begin{pmatrix} \alpha \ \beta \end{pmatrix}, b = \begin{pmatrix} 2 \ 3 \ 5 \end{pmatrix}$$

2. Calculate $A^T A$: $$A^T A = \begin{pmatrix} 1 & 1 & 1 \ 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 1 & 1 \ 1 & 2 \ 1 & 3 \end{pmatrix} = \begin{pmatrix} 3 & 6 \ 6 & 14 \end{pmatrix}$$

3. Calculate $A^T b$: $$A^T b = \begin{pmatrix} 1 & 1 & 1 \ 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 2 \ 3 \ 5 \end{pmatrix} = \begin{pmatrix} 10 \ 23 \end{pmatrix}$$

4. Solve $\begin{pmatrix} 3 & 6 \ 6 & 14 \end{pmatrix} \begin{pmatrix} \alpha \ \beta \end{pmatrix} = \begin{pmatrix} 10 \ 23 \end{pmatrix}$. Using Cramer's rule or inversion, we find $\alpha = 2/3$ and $\beta = 3/2$. The line is $y = 0.67 + 1.5x$.

Worked Example 2: Matrix Inversion

Given $A = \begin{pmatrix} 1 & 0 \ 1 & 1 \ 1 & 2 \end{pmatrix}$ and $b = \begin{pmatrix} 6 \ 0 \ 0 \end{pmatrix}$, find the least squares fit.

1. $A^T A = \begin{pmatrix} 3 & 3 \ 3 & 5 \end{pmatrix}$.
2. $(A^T A)^{-1} = \frac{1}{15-9} \begin{pmatrix} 5 & -3 \ -3 & 3 \end{pmatrix} = \frac{1}{6} \begin{pmatrix} 5 & -3 \ -3 & 3 \end{pmatrix}$.
3. $A^T b = \begin{pmatrix} 6 \ 0 \end{pmatrix}$.
4. $\hat{x} = \frac{1}{6} \begin{pmatrix} 5 & -3 \ -3 & 3 \end{pmatrix} \begin{pmatrix} 6 \ 0 \end{pmatrix} = \begin{pmatrix} 5 \ -3 \end{pmatrix}$.

Common Mistakes

• Ignoring the intercept: Forgetting to include a column of ones in matrix $A$ when fitting a linear model with an intercept term.
• Singular matrices: Attempting to invert $A^T A$ when the columns of $A$ are linearly dependent. Always check for multicollinearity.
• Transposition errors: Confusing $A^T A$ with $A A^T$. Remember that $A^T A$ is always a square $n \times n$ matrix, which is required for solving for $x$.

Frequently Asked Questions

What is the difference between least squares and gradient descent? Least squares is a closed-form analytical solution, while gradient descent is an iterative numerical optimisation algorithm.

When should I use the normal equations? Use them when the number of features is relatively small, as the matrix inversion becomes computationally expensive for very large datasets.

What if $A^T A$ is not invertible? This occurs if the features are perfectly correlated. You may need to remove redundant features or use regularisation techniques like Ridge regression.

Conclusion

Mastering least squares and matrix methods provides a robust foundation for your studies in linear algebra and data science. By understanding the derivation of the normal equations, you can solve complex regression problems with confidence. To see these concepts brought to life with visualisations, generate a free animated lesson on this topic at MathInstructor AI.