---
title: Least-Squares Problems
module: Orthogonality and Least Squares
moduleNumber: 6
lessonNumber: 4
order: 604
summary: >
  When Ax = b has no solution, the least-squares solution makes Ax as close to b
  as possible. The closest Ax is the projection of b onto the column space, and
  the vector that produces it solves the normal equations A-transpose A x =
  A-transpose b. Uniqueness, the residual error, and the stabler QR route follow.
topics: [Orthogonality and Least Squares]
sources:
  - book: Lay
    ref: "§6.5 Least-Squares Problems"
---

Over-determined systems — more equations than unknowns, built from noisy
measurements — usually have no exact solution. The coefficient matrix $A$ maps
$\mathbb{R}^n$ onto the subspace $\operatorname{Col} A$, and the target
$\mathbf{b}$ typically lies outside it, so no exact solution exists. The
practical question is which $\mathbf{x}$ makes $A\mathbf{x}$ closest to
$\mathbf{b}$, and the best-approximation theorem answers it:
project $\mathbf{b}$ onto $\operatorname{Col} A$.

## The least-squares problem

> **Definition (Least-squares solution).** For an $m \times n$ matrix $A$ and
> $\mathbf{b} \in \mathbb{R}^m$, a **least-squares solution** of $A\mathbf{x} =
> \mathbf{b}$ is an $\hat{\mathbf{x}} \in \mathbb{R}^n$ such that
> $$
> \lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert
>   \le \lVert \mathbf{b} - A\mathbf{x} \rVert
>   \quad \text{for all } \mathbf{x} \in \mathbb{R}^n.
> $$

The name records that $\lVert \mathbf{b} - A\mathbf{x} \rVert$ is the square root
of a sum of squares, so minimizing it minimizes the total squared error. No matter
what $\mathbf{x}$ is chosen, $A\mathbf{x}$ lands somewhere in
$\operatorname{Col} A$. The task is to make that point the one in
$\operatorname{Col} A$ nearest to $\mathbf{b}$.

$$
% caption: Every A x lies in the column space of A; the least-squares solution is
% the x whose image A x-hat equals b-hat, the orthogonal projection of b onto Col
% A, so the residual b minus A x-hat is perpendicular to the subspace.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\draw[thick] (-0.5,-0.5) -- (5.5,-0.5) -- (6.3,1.1) -- (0.3,1.1) -- cycle;
\node at (5.9,-0.25) {$\operatorname{Col} A$};
\coordinate (o) at (1.2,0.0);
\coordinate (bh) at (3.4,0.3);
\coordinate (b) at (3.4,2.3);
\coordinate (ax) at (4.9,0.55);
\draw[->, black, very thick] (o) -- (b) node[above right] {$\mathbf{b}$};
\draw[->, acc, very thick] (o) -- (bh) node[below] {$\hat{\mathbf{b}}=A\hat{\mathbf{x}}$};
\draw[->, thick] (o) -- (ax) node[below right] {$A\mathbf{x}$};
\draw[black, thick] (bh) -- (b) node[midway, right] {$\mathbf{b}-A\hat{\mathbf{x}}$};
\draw[black] (3.4,0.5) -- (3.2,0.5) -- (3.2,0.3);
\fill[black] (o) circle (1.6pt);
\end{tikzpicture}
$$

## The normal equations

Let $\hat{\mathbf{b}} = \operatorname{proj}_{\operatorname{Col} A}\mathbf{b}$. It
is in $\operatorname{Col} A$, so $A\mathbf{x} = \hat{\mathbf{b}}$ is consistent and
has a solution $\hat{\mathbf{x}}$. Because $\hat{\mathbf{b}}$ is the closest point
of $\operatorname{Col} A$ to $\mathbf{b}$, this $\hat{\mathbf{x}}$ minimizes
$\lVert \mathbf{b} - A\mathbf{x} \rVert$ and so is a least-squares solution.

The residual $\mathbf{b} - \hat{\mathbf{b}} = \mathbf{b} - A\hat{\mathbf{x}}$ is
orthogonal to $\operatorname{Col} A$, hence orthogonal to every column of $A$. If
$\mathbf{a}_j$ is a column, then $\mathbf{a}_j \cdot (\mathbf{b} -
A\hat{\mathbf{x}}) = 0$, i.e. $\mathbf{a}_j^\top (\mathbf{b} - A\hat{\mathbf{x}}) =
0$. Stacking these over all columns is the single matrix equation
$A^\top (\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}$, which rearranges to
$$
A^\top A\, \mathbf{x} = A^\top \mathbf{b}.
$$

$$
% caption: The normal equations say the residual b minus A x-hat is orthogonal to
% every column of A: it stands perpendicular to the plane spanned by a1 and a2, so
% each dot product with a column vanishes.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\draw[thick] (-0.4,-0.9) -- (4.6,-0.9) -- (5.6,0.6) -- (0.6,0.6) -- cycle;
\node at (2.7,-1.25) {$\operatorname{Col} A$};
\coordinate (o) at (1.4,-0.2);
\draw[->, thick] (o) -- (3.7,-0.45) node[below] {$\mathbf{a}_1$};
\draw[->, thick] (o) -- (2.4,0.15) node[below right] {$\mathbf{a}_2$};
\draw[->, acc, very thick] (o) -- (1.4,2.0) node[above] {residual};
\draw[black] (1.4,0.1) -- (1.62,0.1) -- (1.62,-0.2);
\fill[black] (o) circle (1.6pt);
\end{tikzpicture}
$$

> **Definition (Normal equations).** The **normal equations** for $A\mathbf{x} =
> \mathbf{b}$ are $A^\top A\, \mathbf{x} = A^\top \mathbf{b}$.

> **Theorem (Least-squares solutions via the normal equations).** The set of least-squares solutions of $A\mathbf{x} = \mathbf{b}$
> equals the nonempty set of solutions of the normal equations $A^\top A\,
> \mathbf{x} = A^\top \mathbf{b}$.

The forward direction is the derivation above. Conversely, if $\hat{\mathbf{x}}$
satisfies the normal equations, then $\mathbf{b} - A\hat{\mathbf{x}}$ is
orthogonal to the rows of $A^\top$, hence to the columns of $A$, hence to all of
$\operatorname{Col} A$. So $\mathbf{b} = A\hat{\mathbf{x}} + (\mathbf{b} -
A\hat{\mathbf{x}})$ is an orthogonal decomposition, and by uniqueness
$A\hat{\mathbf{x}}$ must equal the projection $\hat{\mathbf{b}}$ — making
$\hat{\mathbf{x}}$ a least-squares solution. The normal equations convert a
minimization into a square linear system.

> **Worked example.** Solve $A\mathbf{x} = \mathbf{b}$ in the least-squares sense
> for
> $$
> A = \begin{bmatrix} 4 & 0 \\ 0 & 2 \\ 1 & 1 \end{bmatrix},
> \qquad
> \mathbf{b} = \begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix}.
> $$
> The normal-equation pieces are
> $$
> A^\top A = \begin{bmatrix} 17 & 1 \\ 1 & 5 \end{bmatrix},
> \qquad
> A^\top \mathbf{b} = \begin{bmatrix} 19 \\ 11 \end{bmatrix}.
> $$
> Since $A^\top A$ is invertible,
> $$
> \hat{\mathbf{x}} = (A^\top A)^{-1} A^\top \mathbf{b}
>   = \frac{1}{84}\begin{bmatrix} 5 & -1 \\ -1 & 17 \end{bmatrix}
>     \begin{bmatrix} 19 \\ 11 \end{bmatrix}
>   = \begin{bmatrix} 1 \\ 2 \end{bmatrix}.
> $$

### Non-unique least-squares solutions

When the columns of $A$ are dependent, $A\mathbf{x} = \hat{\mathbf{b}}$ has free
variables and the least-squares solutions form a whole family.

> **Worked example.** The $6 \times 4$ system
> $$
> A = \begin{bmatrix}
> 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\
> 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1
> \end{bmatrix},
> \qquad
> \mathbf{b} = (-3, -1, 0, 2, 5, 1),
> $$
> has dependent columns (column $1$ is the sum of columns $2, 3, 4$). Forming the
> normal equations and row reducing gives the general solution
> $$
> \hat{\mathbf{x}} = \begin{bmatrix} 3 \\ -5 \\ -2 \\ 0 \end{bmatrix}
>   + x_4 \begin{bmatrix} -1 \\ 1 \\ 1 \\ 1 \end{bmatrix},
> $$
> with $x_4$ free. Every vector on this line is a least-squares solution, and all
> produce the same $A\hat{\mathbf{x}} = \hat{\mathbf{b}}$.

Such matrices appear in the analysis-of-variance problems of statistics, where the
columns encode overlapping group memberships.

$$
% caption: With dependent columns the least-squares solutions fill a line in the
% domain, yet every point of that line maps to the same projection b-hat in Col A.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black] (-0.3,-1.9) rectangle (3.3,1.9);
\node[black, anchor=south] at (1.5,1.9) {domain $\mathbb{R}^n$};
\draw[acc, thick] (0.2,-1.3) -- (2.8,1.3);
\node[acc, anchor=west] at (0.3,1.5) {solutions};
\fill[acc] (0.8,-0.7) circle (1.4pt);
\fill[acc] (1.5,0.0) circle (1.4pt);
\fill[acc] (2.2,0.7) circle (1.4pt);
\begin{scope}[xshift=6.4cm]
\draw[black] (-0.3,-1.9) rectangle (3.3,1.9);
\node[black, anchor=south] at (1.5,1.9) {codomain $\mathbb{R}^m$};
\draw[thick] (0.2,-1.0) rectangle (2.9,0.2);
\node[anchor=west] at (0.3,-0.4) {$\operatorname{Col} A$};
\fill[black] (1.5,-0.4) circle (1.8pt) node[above] {$\hat{\mathbf{b}}$};
\end{scope}
\draw[->, thick] (3.5,0.5) .. controls (4.6,0.9) and (5.2,0.9) .. (6.1,-0.1)
  node[midway, above, black] {multiply by $A$};
\end{tikzpicture}
$$

## Uniqueness of the least-squares solution

The projection $\hat{\mathbf{b}}$ is unique, but the $\hat{\mathbf{x}}$ producing it
need not be. Uniqueness is governed by the columns of $A$.

> **Theorem (Uniqueness of the least-squares solution).** For an $m \times n$ matrix $A$, the following are equivalent:
> - $A\mathbf{x} = \mathbf{b}$ has a unique least-squares solution for every
>   $\mathbf{b} \in \mathbb{R}^m$.
> - The columns of $A$ are linearly independent.
> - $A^\top A$ is invertible.
>
> In that case the unique solution is
> $\hat{\mathbf{x}} = (A^\top A)^{-1} A^\top \mathbf{b}$.

The equivalence rests on the fact that $\operatorname{Nul}(A^\top A) =
\operatorname{Nul} A$: if $A^\top A\mathbf{x} = \mathbf{0}$, then $\mathbf{x}^\top
A^\top A\mathbf{x} = \lVert A\mathbf{x} \rVert^2 = 0$, so $A\mathbf{x} =
\mathbf{0}$, and the reverse is obvious. Independent columns thus make $A^\top A$
have trivial null space, hence invertible. The closed form
$(A^\top A)^{-1} A^\top \mathbf{b}$ is convenient for a $2 \times 2$ system but is
not the recommended route for larger or ill-conditioned problems.

When the columns are _orthogonal_, no inverse is needed at all: the projection is
the sum of one-dimensional projections, and the weights are the least-squares
solution directly. For $A = [\,\mathbf{a}_1\ \mathbf{a}_2\,]$ with orthogonal
columns,
$$
\hat{\mathbf{b}} = \frac{\mathbf{b}\cdot\mathbf{a}_1}{\mathbf{a}_1\cdot\mathbf{a}_1}\mathbf{a}_1
  + \frac{\mathbf{b}\cdot\mathbf{a}_2}{\mathbf{a}_2\cdot\mathbf{a}_2}\mathbf{a}_2,
\qquad
\hat{\mathbf{x}} = \left(
  \frac{\mathbf{b}\cdot\mathbf{a}_1}{\mathbf{a}_1\cdot\mathbf{a}_1},\
  \frac{\mathbf{b}\cdot\mathbf{a}_2}{\mathbf{a}_2\cdot\mathbf{a}_2}
\right).
$$
> **Worked example.** For $A$ with orthogonal columns
> $\mathbf{a}_1 = (1, 1, 1, 1)$ and $\mathbf{a}_2 = (-6, -2, 1, 7)$ and
> $\mathbf{b} = (-1, 2, 1, 6)$, the two ratios are
> $$
> \frac{\mathbf{b}\cdot\mathbf{a}_1}{\mathbf{a}_1\cdot\mathbf{a}_1} = \frac{8}{4} = 2,
> \qquad
> \frac{\mathbf{b}\cdot\mathbf{a}_2}{\mathbf{a}_2\cdot\mathbf{a}_2} = \frac{45}{90} = \frac{1}{2},
> $$
> so $\hat{\mathbf{x}} = (2, \tfrac{1}{2})$ with no matrix inversion.

Matrices with orthogonal columns arise routinely in the
[regression models](/linear-algebra/orthogonality-least-squares/least-squares-applications)
where centering the data makes the design matrix's columns orthogonal by
construction.

## The least-squares error

Once $\hat{\mathbf{x}}$ is found, the quality of the fit is the distance from
$\mathbf{b}$ to its approximation.

> **Definition (Least-squares error).** The **least-squares error** of
> $\hat{\mathbf{x}}$ is $\lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert$, the minimum
> possible value of $\lVert \mathbf{b} - A\mathbf{x} \rVert$.

For the worked example, $A\hat{\mathbf{x}} = (4, 4, 3)$, so
$\mathbf{b} - A\hat{\mathbf{x}} = (-2, -4, 8)$ and the error is
$\sqrt{4 + 16 + 64} = \sqrt{84}$. No $\mathbf{x}$ can bring $A\mathbf{x}$ within
$\sqrt{84}$ of $\mathbf{b}$; the residual is the leg of the right triangle from
$\mathbf{b}$ down to $\operatorname{Col} A$. An error of zero means $\mathbf{b}$
was already in $\operatorname{Col} A$ and the original system was consistent.

## The QR route

The formula $\hat{\mathbf{x}} = (A^\top A)^{-1} A^\top \mathbf{b}$ can amplify
rounding error: forming $A^\top A$ squares the sensitivity of the problem. When
the columns of $A$ are independent, the
[QR factorization](/linear-algebra/orthogonality-least-squares/gram-schmidt-and-qr)
gives a more reliable path.

> **Theorem (Least-squares solution via QR).** If $A = QR$ is a QR factorization of an $m \times n$ matrix with
> independent columns, then for each $\mathbf{b} \in \mathbb{R}^m$ the unique
> least-squares solution is
> $$
> \hat{\mathbf{x}} = R^{-1} Q^\top \mathbf{b}.
> $$

With $A = QR$, the projection of $\mathbf{b}$ onto $\operatorname{Col} A =
\operatorname{Col} Q$ is $Q Q^\top \mathbf{b}$ (projection onto an orthonormal basis). Then
$A\hat{\mathbf{x}} = QR R^{-1} Q^\top \mathbf{b} = Q Q^\top \mathbf{b} =
\hat{\mathbf{b}}$, so $\hat{\mathbf{x}}$ is the least-squares solution. In
practice one does not invert $R$; since $R$ is upper triangular, the system
$$
R\mathbf{x} = Q^\top \mathbf{b}
$$
is solved by back-substitution, which is faster and more accurate than computing
$R^{-1}$.

$$
% caption: Two routes to the least-squares solution: the normal equations square
% the matrix and can be ill-conditioned, while the QR route projects with Q then
% back-substitutes through the triangular R.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\footnotesize,
  box/.style={draw, black, minimum width=30mm, minimum height=10mm, align=center}]
\definecolor{acc}{HTML}{4A6FA5}
\node[box] (start) at (0,0) {$A\mathbf{x}=\mathbf{b}$\\(inconsistent)};
\node[box] (ne) at (4.6,1.4) {normal equations\\$A^{T} A\mathbf{x}=A^{T}\mathbf{b}$};
\node[box, draw=acc, text=acc] (qr) at (4.6,-1.4) {$QR$ route\\$R\mathbf{x}=Q^{T}\mathbf{b}$};
\node[box] (sol) at (9.2,0) {$\hat{\mathbf{x}}$};
\draw[->, black, thick] (start) -- (ne);
\draw[->, acc, thick] (start) -- (qr);
\draw[->, black, thick] (ne) -- (sol) node[midway, above right] {solve/invert};
\draw[->, acc, thick] (qr) -- (sol) node[midway, below right] {back-substitute};
\end{tikzpicture}
$$

## Summary

| Quantity | Formula | Notes |
| --- | --- | --- |
| Normal equations | $A^\top A\mathbf{x} = A^\top\mathbf{b}$ | always consistent |
| Unique solution | $\hat{\mathbf{x}} = (A^\top A)^{-1}A^\top\mathbf{b}$ | needs independent columns |
| Orthogonal columns | weights $\dfrac{\mathbf{b}\cdot\mathbf{a}_j}{\mathbf{a}_j\cdot\mathbf{a}_j}$ | no inverse needed |
| QR route | $R\mathbf{x} = Q^\top\mathbf{b}$ | back-substitution, more stable |
| Error | $\lVert\mathbf{b}-A\hat{\mathbf{x}}\rVert$ | minimum residual length |

The least-squares solution is a projection: $A\hat{\mathbf{x}}$ is the
foot of the perpendicular from $\mathbf{b}$ to $\operatorname{Col} A$, and the
normal equations are the algebraic statement that the residual is orthogonal to
every column. Fitting lines, polynomials, and surfaces to data applies the same
machinery with $A$ a
[design matrix](/linear-algebra/orthogonality-least-squares/least-squares-applications).[^lay-65]

[^lay-65]: Lay, §6.5 — Least-Squares Problems: the definition of a least-squares solution, Theorem 13 (normal equations), Theorem 14 (uniqueness via independent columns and invertibility of $A^\top A$), the least-squares error, and Theorem 15 (the QR solution $\hat{\mathbf{x}} = R^{-1}Q^\top\mathbf{b}$).