(I) Introduction

Consider the case when \(A\vec{x} = \vec{b}\) has no solution. When an inconsistent system arises in applications and a solution is demanded, the best one can do is to find an \( \vec{x} \) that makes \( A\vec{x} \) as close as possible to \( \vec{b} \).

Since \( ||\vec{b} - A\vec{x}|| \) is the square root of a sum of squares, the least-squares problem is to find an \( \vec{x} \) that makes \( ||\vec{b} - A\vec{x}|| \) as small as possible.

Definition

If \( A \) is an \( m \times n \) matrix and \( \vec{b} \) is in \( \mathbb{R}^m \), a least-squares solution of \( A\vec{x} = \vec{b} \) is a vector \( \hat{x} \) in \( \mathbb{R}^n \) such that:

\[ ||\vec{b} - A\hat{x}|| \le ||\vec{b} - A\vec{x}|| \quad \text{for all } \vec{x} \text{ in } \mathbb{R}^n \]

\( ||\vec{b} - A\hat{x}|| \) is the least-squares error of approximation.

The set of all the vectors \( A\vec{x} \) is \( \text{Col } A \). \( \hat{b} = \text{Proj}_{\text{Col } A} \vec{b} \) is the closest vector in \( \text{Col } A \) to \( \vec{b} \).

If \( \vec{b} \notin \text{Col } A \), then \( \hat{b} \) is in \( \text{Col } A \), so the system \( A\vec{x} = \hat{b} \) is always consistent.

Conclusion: \( \hat{x} \) is a least-squares solution of \( A\vec{x} = \vec{b} \) if and only if \( \hat{x} \) satisfies \( A\hat{x} = \hat{b} \) (Method 1).

A 3D geometric diagram illustrating the concept of a least-squares solution. A flat gray plane represents the column space of matrix A, labeled Col A. A blue vector labeled b points outward, hovering above the plane, indicating it is not in the column space. A red vector labeled b_hat = A x_hat lies flat on the plane, representing the orthogonal projection of b onto Col A. A dashed black line connects the tip of b down to b_hat, labeled b - b_hat. This dashed line forms a mathematically precise right angle with the plane (marked with a square), visually demonstrating that the projection b_hat is the closest point in the column space to the actual vector b.
Figure: The Geometric View of a Least-Squares Solution (\(\hat{b} = A\hat{x}\))

(II) Normal Equations

The orthogonal decomposition theorem (Theorem 8 in Section 6.3) shows that \( \vec{b} - \hat{b} = \vec{b} - A\hat{x} \) is orthogonal to \( \text{Col } A \).

Let \( A = \begin{bmatrix} \vec{a}_1 & \vec{a}_2 & \dots & \vec{a}_n \end{bmatrix} \).

Since \( \vec{b} - A\hat{x} \) is orthogonal to each column of \( A \):

\[ \vec{a}_j \cdot (\vec{b} - A\hat{x}) = 0 \quad \text{for all } j = 1, \dots, n \]

This is equivalent to:

\[ \vec{a}_j^T (\vec{b} - A\hat{x}) = 0 \quad \text{for all } j = 1, \dots, n \]

Writing this as a matrix equation gives:

\[ A^T (\vec{b} - A\hat{x}) = \vec{0} \]

Which simplifies to the normal equation for \( A\vec{x} = \vec{b} \):

\[ A^T A\hat{x} = A^T\vec{b} \]

Theorem 13

The set of least-squares solutions of \( A\vec{x} = \vec{b} \) coincides with the nonempty set of solutions of the normal equations:

\[ A^T A\hat{x} = A^T\vec{b} \quad \text{(Method 2)} \]
Example 1

(1) Find a least-squares solution of the inconsistent system for:

\[ A = \begin{bmatrix} 1 & 3 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}, \quad \vec{b} = \begin{bmatrix} 5 \\ 1 \\ 0 \end{bmatrix} \]

Solution: We compute \( A^T A \) and \( A^T\vec{b} \).

\[ A^T A = \begin{bmatrix} 1 & 1 & 1 \\ 3 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 3 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 3 \\ 3 & 11 \end{bmatrix} \]
\[ A^T\vec{b} = \begin{bmatrix} 1 & 1 & 1 \\ 3 & -1 & 1 \end{bmatrix} \begin{bmatrix} 5 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 6 \\ 14 \end{bmatrix} \]

Now, solve the augmented matrix for the normal equation \( [A^T A \mid A^T\vec{b}] \):

\[ \begin{bmatrix} 3 & 3 & 6 \\ 3 & 11 & 14 \end{bmatrix} \sim \begin{bmatrix} 1 & 1 & 2 \\ 0 & 8 & 8 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \]

There is a unique solution: \( \hat{x} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \).

In fact, if \( A^T A \) is invertible, \( \hat{x} = (A^T A)^{-1}A^T\vec{b} \), and the solution is unique.

(2) Determine the least-squares error in the least-squares solution of \( A\vec{x} = \vec{b} \).

Solution: First compute the estimated vector \( A\hat{x} \):

\[ A\hat{x} = \begin{bmatrix} 1 & 3 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 4 \\ 0 \\ 2 \end{bmatrix} \]

Now compute the error vector \( \vec{b} - A\hat{x} \):

\[ \vec{b} - A\hat{x} = \begin{bmatrix} 5 \\ 1 \\ 0 \end{bmatrix} - \begin{bmatrix} 4 \\ 0 \\ 2 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} \]

The least-squares error is the length of this vector:

\[ ||\vec{b} - A\hat{x}|| = \sqrt{1^2 + 1^2 + (-2)^2} = \sqrt{6} \]

(III) Criteria for Unique Solution

The next theorem gives useful criteria for determining when there is only one least-squares solution of \( A\vec{x} = \vec{b} \).

Theorem 14

Let \( A \) be an \( m \times n \) matrix. The following statements are logically equivalent:

  1. The equation \( A\vec{x} = \vec{b} \) has a unique least-squares solution for each \( \vec{b} \) in \( \mathbb{R}^m \).
  2. The columns of \( A \) are linearly independent.
  3. The matrix \( A^T A \) is invertible.

When these statements are true, the least-squares solution \( \hat{x} \) is given by:

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

Note: This formula is mainly for theoretical proofs, not for typical calculations.

Theoretical Proofs of Theorem 14 (Ex #27-30)

#27 Show \( \text{Nul}(A) = \text{Nul}(A^T A) \).

Proof:

Part 1: \( \text{Nul}(A) \subseteq \text{Nul}(A^T A) \)

If \( \vec{x} \in \text{Nul } A \), then \( A\vec{x} = \vec{0} \), and consequently \( A^T A\vec{x} = A^T\vec{0} = \vec{0} \), which implies that \( \vec{x} \in \text{Nul}(A^T A) \).

Part 2: \( \text{Nul}(A^T A) \subseteq \text{Nul}(A) \)

If \( \vec{x} \in \text{Nul}(A^T A) \), then \( A^T A\vec{x} = \vec{0} \). Left multiply by \( \vec{x}^T \):

\[ \vec{x}^T A^T A\vec{x} = (A\vec{x})^T (A\vec{x}) = (A\vec{x}) \cdot (A\vec{x}) = 0 \implies A\vec{x} = \vec{0} \]

So, \( \vec{x} \in \text{Nul } A \).

#30 Show \( \text{Rank } A = \text{Rank}(A^T A) \).

Proof:

By the Rank Theorem for the \( m \times n \) matrix \( A \):

\[ \text{Rank } A = n - \dim \text{Nul } A \]

By the Rank Theorem for the \( n \times n \) matrix \( A^T A \):

\[ \text{Rank}(A^T A) = n - \dim \text{Nul}(A^T A) \]

Since \( \text{Nul } A = \text{Nul}(A^T A) \) (from #27), their dimensions are equal, so \( \text{Rank } A = \text{Rank}(A^T A) \).

Proving "b iff c" in Theorem 14:

We know \( \text{Rank } A = n \) if and only if the columns of \( A \) are linearly independent.

Since \( \text{Rank}(A^T A) = \text{Rank } A \), we have \( \text{Rank}(A^T A) = n \) if and only if \( \text{Rank } A = n \), which occurs if and only if the columns of \( A \) are linearly independent.

(IV) Method 1: Using Orthogonal Columns

When the columns of \( A \) are orthogonal, we may use Method 1. We find \( \hat{b} \) directly via orthogonal projection and then solve \( A\hat{x} = \hat{b} \).

Example 2

Find a least-squares solution of \( A\vec{x} = \vec{b} \) for:

\[ A = \begin{bmatrix} \vec{v}_1 & \vec{v}_2 \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & 0 \\ 1 & 2 \end{bmatrix}, \quad \vec{b} = \begin{bmatrix} 5 \\ 1 \\ 0 \end{bmatrix} \]

Solution: Note that the columns of \( A \) are orthogonal:

\[ \vec{v}_1 \cdot \vec{v}_2 = 1(-2) + 1(0) + 1(2) = 0 \]

Thus, \( \{\vec{v}_1, \vec{v}_2\} \) is an orthogonal basis for \( \text{Col } A \).

Compute the projection \( \hat{b} = \text{Proj}_{\text{Col } A} \vec{b} \):

\[ \hat{b} = \frac{\vec{b} \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 + \frac{\vec{b} \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2}\vec{v}_2 \]
\[ \hat{b} = \frac{6}{3}\vec{v}_1 + \frac{8}{8}\vec{v}_2 = 2\vec{v}_1 + \vec{v}_2 \]

Now solve \( A\hat{x} = \hat{b} \):

Since \( \hat{b} = 2\vec{v}_1 + 1\vec{v}_2 \) is already written as a linear combination of the columns of \( A \), the weights are simply the entries of \( \hat{x} \).

\[ \hat{x} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \]

Theorem 15

Given an \( m \times n \) matrix \( A \) with linearly independent columns. Let \( A = QR \) be a QR factorization of \( A \) as in Theorem 12 (in Section 6.4).

Then for each \( \vec{b} \) in \( \mathbb{R}^m \), the equation \( A\vec{x} = \vec{b} \) has a unique least-squares solution given by:

\[ \hat{x} = R^{-1}Q^T\vec{b} \]