Least Squares
Solutions

Learn how to find the best approximate solution when a system \( A\mathbf{x} = \mathbf{b} \) has no exact solution: the foundation of data fitting and regression.

Linear Algebra

What Is an Overdetermined System?

An overdetermined system \( A\mathbf{x} = \mathbf{b} \) has more equations than unknowns: the matrix \( A \) is \( m \times n \) with \( m > n \). Typically, no vector \( \mathbf{x} \) satisfies every equation simultaneously.

Equations

\( m \) rows in \( A \): each row is one constraint on \( \mathbf{x} \).

Unknowns

\( n \) columns in \( A \): fewer degrees of freedom than constraints.

Result

\( \mathbf{b} \) usually lies outside \(\text{Col}(A)\), so no exact solution exists.

The Geometric Picture

Why Least Squares Matters

Whenever real-world data doesn't perfectly fit a model, least squares gives us the best fit. It underpins statistics, engineering, machine learning, and every line-of-best-fit you've ever drawn.

Linear Regression

Fitting a line \( y = mx + c \) through scattered data points.

Signal Processing

Extracting a clean signal from noisy measurements.

GPS Navigation

Using more satellites than unknowns to pinpoint location accurately.

The Normal Equation

This equation comes directly from the condition that the residual \( \mathbf{b} - A\hat{\mathbf{x}} \) must be orthogonal to every column of \( A \): that is, \( A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} \).

Deriving the Normal Equation

1

Goal: Minimize \( \| \mathbf{b} - A\mathbf{x} \|^2 \). This is the sum of squared residuals.

2

Orthogonality condition: The minimum occurs when the residual \( \mathbf{b} - A\hat{\mathbf{x}} \) is orthogonal to \( \text{Col}(A) \).

3

Translate: \( \mathbf{b} - A\hat{\mathbf{x}} \perp \text{Col}(A) \) means \( A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} \).

4

Rearrange: \( A^T A \, \hat{\mathbf{x}} = A^T \mathbf{b} \). This is the normal equation.

Exact vs. Least Squares

	Exact Solution	Least Squares Solution
System	\( A\mathbf{x} = \mathbf{b} \)	\( A^T A \, \hat{\mathbf{x}} = A^T \mathbf{b} \)
When it exists	\( \mathbf{b} \in \text{Col}(A) \)	Always (for any \( \mathbf{b} \))
Residual	\( \mathbf{0} \)	Minimized \( \\| \mathbf{b} - A\hat{\mathbf{x}} \\| \)
Uniqueness	Depends on \( \text{null}(A) \)	Unique when cols of \( A \) are independent

How to Solve a Least Squares Problem

1

Compute \( A^T A \): Multiply the transpose of \( A \) by \( A \). The result is an \( n \times n \) symmetric matrix.

2

Compute \( A^T \mathbf{b} \): Multiply \( A^T \) by the right-hand side vector \( \mathbf{b} \).

3

Solve \( A^T A \, \hat{\mathbf{x}} = A^T \mathbf{b} \): Use row reduction or the inverse of \( A^T A \) (if invertible).

4

Verify: Check that \( \mathbf{b} - A\hat{\mathbf{x}} \) is orthogonal to the columns of \( A \): \( A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} \).

Worked Example: Simple System

Find the least squares solution of \( A\mathbf{x} = \mathbf{b} \) where:

Step 1: Compute \( A^T A \):

Example 1: Completing the Solve

Step 2: Compute \( A^T \mathbf{b} \):

Step 3: Solve \( A^T A \, \hat{\mathbf{x}} = A^T \mathbf{b} \):

Visualizing the Best Fit Line

Example 2: Larger System

Find the least squares solution of:

1

\( A^T A = \begin{bmatrix} 4 & 6 \\ 6 & 14 \end{bmatrix} \), \( A^T \mathbf{b} = \begin{bmatrix} 8 \\ 17 \end{bmatrix} \)

2

Solve: \( \hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b} = \begin{bmatrix} -1/10 \\ 13/10 \end{bmatrix} \)

3

Best-fit line: \( y = -0.1 + 1.3\,t \)

The Projection Matrix

The matrix that projects any vector onto \( \text{Col}(A) \) is:

\( P^2 = P \)

Projecting twice gives the same result: \( P \) is idempotent.

\( P^T = P \)

The projection matrix is always symmetric.

The Residual Vector

1

\( \mathbf{r} \) is in \( \text{Col}(A)^{\perp} \): it is orthogonal to every column of \( A \).

2

\( \| \mathbf{b} \|^2 = \| A\hat{\mathbf{x}} \|^2 + \| \mathbf{r} \|^2 \) (Pythagorean theorem in \( \mathbb{R}^m \)).

3

If \( \| \mathbf{r} \| = 0 \), then \( \mathbf{b} \in \text{Col}(A) \) and the exact solution exists.

Common Mistakes

✕ Forgetting the Transpose

Writing \( AA\,\hat{\mathbf{x}} = A\mathbf{b} \) instead of \( A^T A\,\hat{\mathbf{x}} = A^T\mathbf{b} \). You must multiply both sides by \( A^T \).

✕ Inverting \( A \) Directly

Trying to compute \( A^{-1} \) when \( A \) is not square. Only \( A^T A \) (an \( n \times n \) matrix) can be inverted.

✕ Wrong Multiplication Order

Computing \( AA^T \) instead of \( A^T A \). These are different sizes: \( A^T A \) is \( n \times n \), while \( AA^T \) is \( m \times m \).

Summary of Key Formulas

Concept	Formula	Meaning
Normal equation	\( A^T A\,\hat{\mathbf{x}} = A^T\mathbf{b} \)	Defines \( \hat{\mathbf{x}} \)
Explicit solution	\( \hat{\mathbf{x}} = (A^T A)^{-1}A^T\mathbf{b} \)	When cols independent
Projection	\( \hat{\mathbf{b}} = A\hat{\mathbf{x}} \)	Closest point in Col(\(A\))
Residual	\( \mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}} \)	\( \mathbf{r} \perp \text{Col}(A) \)
Projection matrix	\( P = A(A^T A)^{-1}A^T \)	\( P^2 = P \), \( P^T = P \)

Question 1 of 5

The least squares solution \( \hat{\mathbf{x}} \) of \( A\mathbf{x} = \mathbf{b} \) satisfies which equation?

The normal equation is \( A^T A\,\hat{\mathbf{x}} = A^T\mathbf{b} \). It is derived by multiplying both sides of the orthogonality condition by \( A^T \).

Question 2 of 5

If \( A \) is a \( 5 \times 3 \) matrix, what is the size of \( A^T A \)?

\( A^T \) is \( 3 \times 5 \) and \( A \) is \( 5 \times 3 \), so \( A^T A \) is \( 3 \times 3 \). The result is always \( n \times n \) where \( n \) is the number of columns of \( A \).

Question 3 of 5

The residual vector \( \mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}} \) is orthogonal to which subspace?

The residual \( \mathbf{r} \) lies in \( \text{Col}(A)^{\perp} \), meaning it is orthogonal to every vector in the column space of \( A \). This is the defining property of the least squares solution.

Question 4 of 5

Given \( A = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \) and \( \mathbf{b} = \begin{bmatrix} 3 \\ 1 \end{bmatrix} \), what is \( \hat{x} \)?

\( A^T A = [1\ 2]\begin{bmatrix}1\\2\end{bmatrix} = 5 \) and \( A^T\mathbf{b} = [1\ 2]\begin{bmatrix}3\\1\end{bmatrix} = 5 \). So \( \hat{x} = 5/5 = 1 \).

Question 5 of 5

Which property does the projection matrix \( P = A(A^T A)^{-1}A^T \) always satisfy?

A projection matrix is always idempotent (\( P^2 = P \)) and symmetric (\( P^T = P \)). It is generally not invertible (its determinant is 0 unless it projects onto the full space).