Lesson 5.1: The Inexact Problem: Why Ax=b Often Has No Solution

Welcome to the messy, noisy, but far more realistic world of data.

Welcome to Module 5. We are now stepping out of the clean, theoretical world of perfect mathematical systems and into the messy, noisy, but far more realistic world of data.

In our journey so far, when we solved `Ax=b`, we implicitly assumed that a perfect solution existed. But in almost every practical application—from economics to machine learning, from engineering to biology—the single most common answer to the question "Does `Ax=b` have a solution?" is a resounding NO.

Today, we will understand why this is the case, what it means, and how it forces us to redefine our entire concept of a "solution."

The Reality of Data: Overdetermined Systems

Imagine you are a scientist trying to find a linear relationship, `y = mx + c`, between two variables. You run an experiment and collect some data points.

Experiment Data
x (Temperature)y (Pressure)
11
23
32

Each data point gives us one equation:

  • For (1, 1): m(1)+c=1m(1) + c = 1
  • For (2, 3): m(2)+c=3m(2) + c = 3
  • For (3, 2): m(3)+c=2m(3) + c = 2

Let's write this in our familiar `Ax=b` form. Our unknowns are `m` and `c`, so our unknown vector is `x = [m, c]ᵀ`.

[112131]⏟A[mc]⏟x=[132]⏟b\underbrace{\begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \end{bmatrix}}_{A} \underbrace{\begin{bmatrix} m \\ c \end{bmatrix}}_{x} = \underbrace{\begin{bmatrix} 1 \\ 3 \\ 2 \end{bmatrix}}_{b}

Notice the dimensions. `A` is a `3x2` matrix. We have 3 equations but only 2 unknowns. This is an overdetermined system. We have more constraints (data points) than we have degrees of freedom (parameters). Unless your data is perfectly, miraculously linear (which real data never is), it's impossible for all three lines to intersect at a single point.

The New Goal: Get as Close as Possible

If `Ax=b` has no solution, we must change our goal. We now seek an `x` that makes `Ax` as close to `b` as possible.

We define the error vector `e` as the difference between what we want (`b`) and what we get (`Ax`).

e=b−Axe = b - Ax

The official goal of Least Squares is to find the special vector `x̂` ("x-hat") that minimizes the squared length of the error vector:

Find x^ that minimizes ∥b−Ax∥2\text{Find } \hat{x} \text{ that minimizes } \|b - Ax\|^2

This `x̂` is our best approximate solution. For our problem, it will give us the line of best fit.

The Geometric Insight: Projection

An exact solution exists only if `b` is in the Column Space of A. When there's no solution, it means `b` is outside of `C(A)`. In our example, `C(A)` is a plane in 3D space, and `b` is a point not on that plane.

The closest point to `b` within the Column Space is its orthogonal projection onto that subspace. Let's call this projection vector `p`.

The new, solvable quest is: Find `x̂` such that `Ax̂ = p`.

The error vector `e = b - p` will be orthogonal to the Column Space, a crucial fact we will use to find the solution.

Summary: The Key Ideas
  • The Reality: Most real-world systems are overdetermined and have no exact solution.
  • The New Goal: Find the least-squares solution `x̂` that minimizes the error `||b - Ax||²`.
  • The Geometry: This is equivalent to finding the orthogonal projection `p` of `b` onto the Column Space of `A` and solving `Ax̂ = p`.
Previous
Lesson 4.6: The Cholesky Decomposition (LLᵀ)
Next
Lesson 5.2: The Geometry of "Best Fit": Projections