01 / 20

Normal Equations
and Geometric Interpretation

Learn how to solve least-squares problems using the normal equations, and see why the solution is a projection onto the column space.

Linear Algebra

What Problem Are We Solving?

In many real-world scenarios we encounter a system \( A\mathbf{x} = \mathbf{b} \) that has no exact solution: there are more equations than unknowns. We need the best approximate solution: the vector \( \hat{\mathbf{x}} \) that makes \( A\hat{\mathbf{x}} \) as close to \( \mathbf{b} \) as possible.

The Column Space Intuition

The product \( A\mathbf{x} \) is a linear combination of the columns of \( A \). As \( \mathbf{x} \) varies, \( A\mathbf{x} \) sweeps out the column space \( \text{Col}(A) \). If \( \mathbf{b} \) is not in \( \text{Col}(A) \), the closest point in that subspace is its orthogonal projection.

\( \text{Col}(A) \)
\( \mathbf{b} \)
\( A\hat{\mathbf{x}} \)
\( \mathbf{b} - A\hat{\mathbf{x}} \)
\( \mathbf{0} \)

Why "Normal"?

The word "normal" here means perpendicular. The normal equations enforce the condition that the error vector is normal (perpendicular) to every column of \( A \).

Normal in Geometry
A vector perpendicular to a surface or subspace.
Normal Equations
Equations ensuring the residual is perpendicular to \( \text{Col}(A) \).

The Normal Equations

Starting from the orthogonality condition:

If the columns of \( A \) are linearly independent, then \( A^T A \) is invertible and the unique solution is:

The Projection Matrix

The projected vector \( \hat{\mathbf{b}} = A\hat{\mathbf{x}} \) can be written as \( P\mathbf{b} \) where:

\( P^2 = P \)
Projecting twice gives the same result: \( P \) is idempotent.
\( P^T = P \)
\( P \) is symmetric: projection preserves inner products.
\( I - P \)
Projects onto the orthogonal complement (the residual part).

Normal Equations vs. Other Methods

Normal Equations QR Factorization SVD
Formula \( (A^TA)^{-1}A^T\mathbf{b} \) \( R^{-1}Q^T\mathbf{b} \) Via pseudoinverse
Speed Fast Moderate Slower
Stability Can be poor Good Best
Handles rank-deficient? No Partially Yes

How to Apply the Normal Equations

1
Form \( A^T A \). Multiply the transpose of \( A \) by \( A \) itself. This gives a square \( n \times n \) matrix.
2
Form \( A^T \mathbf{b} \). Multiply the transpose of \( A \) by the right-hand side vector \( \mathbf{b} \).
3
Solve \( A^T A \, \hat{\mathbf{x}} = A^T \mathbf{b} \). Use Gaussian elimination, Cholesky factorization, or (for small systems) direct inversion.
4
Verify. Check that the residual \( \mathbf{b} - A\hat{\mathbf{x}} \) is orthogonal to every column of \( A \): \( A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0} \).

Example 1: Fitting a Constant

Find the least-squares solution to \( A\mathbf{x} = \mathbf{b} \) where \( A = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \) and \( \mathbf{b} = \begin{bmatrix} 2 \\ 4 \\ 6 \end{bmatrix} \).

Example 1: Geometric View

\( \text{Col}(A) \)
\( \mathbf{0} \)
\( \mathbf{b} = \begin{bsmallmatrix}2\\4\\6\end{bsmallmatrix} \)
\( A\hat{\mathbf{x}} = \begin{bsmallmatrix}4\\4\\4\end{bsmallmatrix} \)
\( \mathbf{e} \)

Example 2: Best-Fit Line

Fit a line \( y = c + dt \) through the points \( (0, 1) \), \( (1, 3) \), \( (2, 4) \). We set up:

Example 2: Visualizing the Fit

t y 0 1 2 1 2 3 4 Data Fit

Example 3: Overdetermined System

Solve \( A\mathbf{x}=\mathbf{b} \) in the least-squares sense:
\( A = \begin{bmatrix}1&1\\1&2\\1&3\end{bmatrix},\quad \mathbf{b}=\begin{bmatrix}1\\2\\2\end{bmatrix} \)

Calculus Derivation

We can also derive the normal equations by minimizing the cost function using calculus:

When Does \( A^TA \) Fail to Be Invertible?

\( A^TA \) is invertible if and only if the columns of \( A \) are linearly independent. This fails when:

Redundant Columns
One column is a scalar multiple or linear combination of others.
More Unknowns
\( n > m \): underdetermined system, infinitely many least-squares solutions.

Common Mistakes

✕ Wrong Order
Writing \( AA^T\hat{\mathbf{x}} = A\mathbf{b} \) instead of \( A^TA\hat{\mathbf{x}} = A^T\mathbf{b} \). The transpose goes on the left factor.
✕ Forgetting Both Sides
Multiplying only the left side by \( A^T \) and leaving \( \mathbf{b} \) unchanged. Both sides must be multiplied: \( A^T(A\mathbf{x}) = A^T\mathbf{b} \).
✕ Assuming Invertibility
Using \( (A^TA)^{-1} \) without checking that columns of \( A \) are linearly independent.

Question 1 of 5

The normal equations for the least-squares problem \( A\mathbf{x} = \mathbf{b} \) are:

Question 2 of 5

If \( A = \begin{bmatrix}1\\1\\1\end{bmatrix} \) and \( \mathbf{b} = \begin{bmatrix}3\\5\\7\end{bmatrix} \), what is the least-squares solution \( \hat{x} \)?

Question 3 of 5

The projection matrix \( P = A(A^TA)^{-1}A^T \) satisfies which two properties?

Question 4 of 5

The residual vector \( \mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}} \) from the least-squares solution is orthogonal to:

Question 5 of 5

A disadvantage of the normal equations compared to QR factorization is: