7.812 min read

The Least Squares Problem

Most real-world systems are overdetermined: you have more equations than unknowns. A GPS receiver solves ~30 satellite equations for 4 unknowns; a data scientist fits a line through thousands of points. There is usually no exact solution $Ax = b$ , so we ask: what $x$ makes $Ax$ as close as possible to $b$ ?

We measure closeness with the Euclidean norm: the residual is $r = b - Ax$ , and its length $\|r\|$ is the error. The least squares problem asks us to minimize $\|b - Ax\|^2$ over all $x \in \mathbb{R}^n$ .

Geometrically, $Ax$ can only reach the column space of $A$ . The closest point in the column space to $b$ is the orthogonal projection $\hat{b} = \text{proj}_{\text{col}(A)} b$ . The optimal $\hat{x}$ satisfies $A\hat{x} = \hat{b}$ .

Since $b - A\hat{x}$ must be perpendicular to every column of $A$ , we get the condition $A^T(b - A\hat{x}) = 0$ , which rearranges to the normal equations $A^T A \hat{x} = A^T b$ . We will solve these in section 7.9.

Formal View

Definition 7.8 — Least Squares Solution

Given

A \in \mathbb{R}^{m \times n}

with

m > n

and

b \in \mathbb{R}^m

, the least squares solution

\hat{x}

minimizes

\|b - Ax\|^2 = \sum_{i=1}^m (b_i - (Ax)_i)^2.

It satisfies

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

(the normal equations).

Theorem 7.8 — Existence and Uniqueness

A least squares solution always exists. It is unique if and only if

A

has full column rank (i.e., the columns of

A

are linearly independent), in which case

A^T A

is invertible and

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

Why This Matters

Least squares is the backbone of data fitting and statistical estimation, appearing everywhere from GPS to machine learning.

Linear regression: fitting the best line or plane through data
Navigation systems: estimating position from overdetermined satellite equations
Signal processing: filtering and denoising noisy measurements
Computer vision: fitting geometric models to point clouds

Learning Resources

Least Squares, in the World of Lines

3Blue1Brown

Geometric intuition for why the normal equations work.

15 min

Least Squares Approximation

MIT OpenCourseWare

Gilbert Strang derives the normal equations from the projection perspective.

48 min

Quiz

Question 1

The least squares solution $\hat{x}$ minimizes which quantity?

Question 2

A least squares solution exists for every matrix $A$ and every vector $b$ .

Question 3

If $A \in \mathbb{R}^{m \times n}$ with $m > n$ has full column rank, the unique least squares solution is:

Common Mistakes

Trying to solve $Ax = b$ directly when $m > n$ — this system is generally inconsistent; use the normal equations instead.
Forgetting that the normal equations require $A$ to have full column rank; if columns are dependent, $A^T A$ is singular.
Confusing minimizing $\|b - Ax\|$ with minimizing $\|Ax - b\|^2$ — they give the same answer, but squaring makes the algebra smoother.