Why Least Squares

Suppose we collect a few data points and want to fit a simple curve through them. With exactly as many data points as parameters, we can do this precisely. But what happens when we have more data points than parameters? That is the situation the least squares method is designed for.

---

The Problem: More Equations Than Unknowns

Consider three data points:

$$(x_1, y_1) = (1,\, 1), \quad (x_2, y_2) = (2,\, 3), \quad (x_3, y_3) = (3,\, 2)$$

We want to fit a straight line $P_1(x) = a_0 + a_1 x$ through all three points. Substituting each point gives three equations:

$$a_0 + a_1 (1) = 1$$ $$a_0 + a_1 (2) = 3$$ $$a_0 + a_1 (3) = 2$$

In matrix form $Ax = b$:

$$\underbrace{\begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}}_{A} \underbrace{\begin{bmatrix} a_0 \\ a_1 \end{bmatrix}}_{x} = \underbrace{\begin{bmatrix} 1 \\ 3 \\ 2 \end{bmatrix}}_{b}$$

We have 3 equations but only 2 unknowns. The matrix $A$ is $3 \times 2$, not square. There is no vector $x$ that satisfies all three equations simultaneously — the three points do not lie on any single straight line.

Note

A system is overdetermined when the number of equations $m$ is greater than the number of unknowns $n$, so $A$ is an $m \times n$ matrix with $m > n$. Overdetermined systems typically have no exact solution.

---

Residuals and the Best Fit

Since an exact solution does not exist, we settle for the best approximate one. For any candidate $x = (a_0, a_1)^T$, the vector $Ax$ gives predicted values, while $b$ gives the actual values. The difference at each point is called the residual:

$$r_i = b_i - (Ax)_i$$

For our three-point example:

$$r_1 = 1 - (a_0 + a_1), \quad r_2 = 3 - (a_0 + 2a_1), \quad r_3 = 2 - (a_0 + 3a_1)$$

In vector form, the residual vector is:

$$r = b - Ax$$

We want $x$ to make these residuals as small as possible. A natural measure is the sum of squared residuals:

$$E = r_1^2 + r_2^2 + r_3^2 = \sum_{i=1}^{m} r_i^2 = \|b - Ax\|^2$$

The least squares method finds the $x$ that minimizes $E$. This is why the method is called “least squares” — we are minimizing the sum of the squares of the residuals.

---

Geometric Interpretation

Geometrically, $Ax$ ranges over all vectors in the column space of $A$ as $x$ varies. The vector $b$ generally lies outside this column space (since the system is overdetermined). The least squares solution finds the point in the column space closest to $b$, which is the orthogonal projection of $b$ onto the column space of $A$.

The residual vector $r = b - Ax$ at the optimal $x$ is perpendicular to every column of $A$:

$$A^T(b - Ax) = 0 \quad \Longrightarrow \quad A^T A x = A^T b$$

This is the key equation of the least squares method, called the normal equations, derived formally in the next section.

---

What is an Overdetermined System?

An overdetermined system arises whenever we have more constraints than degrees of freedom. A concrete example: suppose we have a $3 \times 3$ system (same number of equations and unknowns):

$$5x_1 + 2x_2 + 3x_3 = 7$$ $$2x_1 + 7x_2 + 8x_3 = 5$$ $$3x_1 + 9x_2 + 2x_3 = 6$$

This can be solved directly by Gaussian elimination, LU decomposition, or an inverse matrix because $A$ is $3 \times 3$ and square. Now suppose a fourth equation is added:

$$5x_1 + 2x_2 + 3x_3 = 7$$ $$2x_1 + 7x_2 + 8x_3 = 5$$ $$3x_1 + 9x_2 + 2x_3 = 6$$ $$4x_1 + 2x_2 + 5x_3 = 10$$

The coefficient matrix is now:

$$A = \begin{bmatrix} 5 & 2 & 3 \\ 2 & 7 & 8 \\ 3 & 9 & 2 \\ 4 & 2 & 5 \end{bmatrix}$$

This is a $4 \times 3$ matrix. It is not square, so Gaussian elimination, LU decomposition, and the inverse matrix method cannot be applied directly. The number of equations (4) is greater than the number of unknowns (3). This is an overdetermined system, and the least squares method gives us a principled way to find the best approximate solution.