Linear Algebra › Section F · Orthogonality and least squares › Topic F.5

Least-squares problems

Measurements carry errors, so a system with more equations than unknowns usually has no exact solution. Least squares finds the next best thing: the vector that comes as close as possible to solving it, using the projections of this section.

When Ax = b has no solution

Suppose you take ten measurements to pin down two unknowns. Each measurement gives one linear equation, so you have ten equations in two unknowns, and because every measurement is slightly off, no single \(\mathbf{x}\) satisfies them all. Row reduction would only report that the system is inconsistent. That answer is correct but useless. A better question is: which \(\mathbf{x}\) makes \(A\mathbf{x}\) as close as possible to \(\mathbf{b}\)? Distances in \(\mathbb{R}^m\), from "Inner product, length, and orthogonality", make the question precise, and projections answer it.

What a least-squares solution is

Let \(A\) be \(m \times n\) and \(\mathbf{b}\) in \(\mathbb{R}^m\). A least-squares solution of \(A\mathbf{x} = \mathbf{b}\) is a vector \(\hat{\mathbf{x}}\) in \(\mathbb{R}^n\) such that

\|\mathbf{b} - A\hat{\mathbf{x}}\| \le \|\mathbf{b} - A\mathbf{x}\|

for every \(\mathbf{x}\) in \(\mathbb{R}^n\). The name comes from the square of this distance: \(\|\mathbf{b} - A\mathbf{x}\|^2\) is the sum of the squares of the entries of \(\mathbf{b} - A\mathbf{x}\), and \(\hat{\mathbf{x}}\) makes that sum as small as possible. The vector \(\mathbf{b} - A\hat{\mathbf{x}}\) is the residual vector, and its length is the least-squares error. If the system happens to be consistent, the least-squares solutions are just the ordinary solutions, with error 0.

The geometry: project b onto Col A

As \(\mathbf{x}\) varies, \(A\mathbf{x}\) runs over exactly the column space \(\operatorname{Col} A\). So the question becomes: which vector of \(\operatorname{Col} A\) is closest to \(\mathbf{b}\)? The best approximation theorem from "Orthogonal projections" answers it:

\hat{\mathbf{b}} = \operatorname{proj}_{\operatorname{Col} A} \mathbf{b}

Because \(\hat{\mathbf{b}}\) lies in \(\operatorname{Col} A\), the equation \(A\mathbf{x} = \hat{\mathbf{b}}\) is always consistent, and its solutions are precisely the least-squares solutions. The residual \(\mathbf{b} - \hat{\mathbf{b}}\) is the perpendicular piece of the orthogonal decomposition of \(\mathbf{b}\), so it lies in \((\operatorname{Col} A)^\perp\).

The normal equations

Computing \(\hat{\mathbf{b}}\) directly would need an orthogonal basis of \(\operatorname{Col} A\). There is a shortcut. The residual \(\mathbf{b} - A\hat{\mathbf{x}}\) is orthogonal to every column of \(A\), so its inner product with each column is zero. Stacking those conditions gives \(A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}\), which rearranges to

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

These are the normal equations. The reasoning also runs backwards, so the least-squares solutions of \(A\mathbf{x} = \mathbf{b}\) are exactly the solutions of the normal equations, and that set is never empty. Note the sizes: \(A^TA\) is a small \(n \times n\) matrix even when \(A\) is tall.

Worked example: a 3 × 2 inconsistent system

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

A = \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 5 \\ -1 \\ 1 \end{bmatrix}

1. Form

A^TA = \begin{bmatrix} 5 & 2 \\ 2 & 2 \end{bmatrix}

and \(A^T\mathbf{b} = (9, 6)\). 2. Solve \(5x_1 + 2x_2 = 9\) and \(2x_1 + 2x_2 = 6\): subtracting gives \(3x_1 = 3\), so \(\hat{\mathbf{x}} = (1, 2)\). 3. Residual: \(A\hat{\mathbf{x}} = (4, 1, 2)\), so \(\mathbf{b} - A\hat{\mathbf{x}} = (1, -2, -1)\). 4. Check: the residual has inner product \(2 - 2 + 0 = 0\) with column 1 and \(1 + 0 - 1 = 0\) with column 2. 5. Least-squares error: \(\sqrt{1 + 4 + 1} = \sqrt{6} \approx 2.45\).

When the solution is unique

For an \(m \times n\) matrix \(A\), three statements are equivalent: \(A\mathbf{x} = \mathbf{b}\) has exactly one least-squares solution for every \(\mathbf{b}\); the columns of \(A\) are linearly independent; and \(A^TA\) is invertible. Then

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

and the projection is \(\hat{\mathbf{b}} = A(A^TA)^{-1}A^T\mathbf{b}\), although solving the normal equations by row reduction is usually quicker than inverting. With dependent columns there are infinitely many least-squares solutions, all giving the same \(\hat{\mathbf{b}}\). For columns \((1, 1, 1)\) and \((2, 2, 2)\) with \(\mathbf{b} = (1, 2, 6)\), the normal equations reduce to \(x_1 + 2x_2 = 3\): a whole line of solutions, every one giving \(A\hat{\mathbf{x}} = (3, 3, 3)\).

Using a QR factorisation

Forming \(A^TA\) can lose accuracy on a computer, because small relative errors in the data can grow much larger in \(A^TA\) than in \(A\) itself. If \(A = QR\), as in "The Gram-Schmidt process and QR", substitute into the normal equations: \(R^TQ^TQR\hat{\mathbf{x}} = R^TQ^T\mathbf{b}\). Since \(Q^TQ = I\) and \(R^T\) is invertible, this simplifies to

R\hat{\mathbf{x}} = Q^T\mathbf{b}

Because \(R\) is upper triangular, back substitution solves it at once. QR is a standard way for software to solve least-squares problems; for nearly dependent columns the singular value decomposition, met in "The singular value decomposition", is safer. Another remedy, ridge regression, adds a penalty \(\lambda\|\mathbf{x}\|^2\) to the squared error to keep such problems stable.

Worked example: least squares by QR

Use the factorisation \(A = QR\) from the previous topic, where \(A\) has columns \((1, 1, 1, 1)\), \((3, 1, 3, 1)\), \((4, 0, 2, 2)\), and take \(\mathbf{b} = (1, 3, 1, -1)\). 1. Compute \(Q^T\mathbf{b}\): \(\frac{1}{2}(1 + 3 + 1 - 1) = 2\), \(\frac{1}{2}(1 - 3 + 1 + 1) = 0\), \(\frac{1}{2}(1 - 3 - 1 - 1) = -2\). 2. Back substitute in \(R\hat{\mathbf{x}} = (2, 0, -2)\): \(2x_3 = -2\) gives \(x_3 = -1\); \(2x_2 + 2x_3 = 0\) gives \(x_2 = 1\); \(2x_1 + 4x_2 + 4x_3 = 2\) gives \(x_1 = 1\). 3. So \(\hat{\mathbf{x}} = (1, 1, -1)\) and \(A\hat{\mathbf{x}} = (0, 2, 2, 0)\). 4. Check: the residual \((1, 1, -1, -1)\) is orthogonal to all three columns, and the error is \(\sqrt{4} = 2\).

A short history

Adrien-Marie Legendre published the method of least squares in 1805, and Carl Friedrich Gauss, who said he had used it since the 1790s, developed its theory. Gauss's best-known early success came in 1801, when he predicted where astronomers should look for the newly discovered dwarf planet Ceres after they had lost track of it. The method suited such problems perfectly: many imprecise observations, a few unknown orbital quantities, and a need for the single best compromise. Today the same computation fits lines to data, calibrates instruments and positions satellite navigation receivers.

Common mistakes to avoid

First, solving \(A^TA\hat{\mathbf{x}} = \mathbf{b}\): the right side is \(A^T\mathbf{b}\), and the sizes would not even match. Second, choosing a square subset of the equations and solving it exactly; that ignores the other data and is generally not the least-squares solution. Third, writing \(\hat{\mathbf{x}} = A^{-1}\mathbf{b}\) for a non-square \(A\). Fourth, using \((A^TA)^{-1}\) when the columns of \(A\) are dependent; then \(A^TA\) is singular and the solutions form a family. Fifth, reporting \(\|A\hat{\mathbf{x}}\|\) as the error; the error is \(\|\mathbf{b} - A\hat{\mathbf{x}}\|\).

Key takeaways

A least-squares solution \(\hat{\mathbf{x}}\) minimises \(\|\mathbf{b} - A\mathbf{x}\|\), the square root of the sum of squared residuals. Geometrically, \(A\hat{\mathbf{x}}\) is the projection of \(\mathbf{b}\) onto \(\operatorname{Col} A\), and the residual is orthogonal to every column of \(A\). This gives the normal equations \(A^TA\hat{\mathbf{x}} = A^T\mathbf{b}\), which always have a solution. The solution is unique exactly when the columns of \(A\) are independent, and then \(\hat{\mathbf{x}} = (A^TA)^{-1}A^T\mathbf{b}\). With \(A = QR\), solve \(R\hat{\mathbf{x}} = Q^T\mathbf{b}\) by back substitution, which is more accurate in practice.

Flashcards

Flashcard

Least-squares solution x̂

Makes ‖b - Ax̂‖ ≤ ‖b - Ax‖ for every x

Minimises the sum of squared residuals.

Test your understanding

Question 1 of 5

Which equations must every least-squares solution x̂ of Ax = b satisfy?

Question 2 of 5

A has rows (1, 0), (0, 1), (1, 1), and b = (1, 1, 0). What is the least-squares solution x̂?

Question 3 of 5

For a least-squares solution x̂ of Ax = b, the residual b - Ax̂ is orthogonal to which of these?

Question 4 of 5

When does Ax = b have exactly one least-squares solution for every b?

Question 5 of 5

A has independent columns and A = QR. Which equation gives the least-squares solution x̂?

← Previous topicNext topic →