Orthogonal Projections, Least Squares, and QR

An exact system $A\mathbf x=\mathbf b$ may be inconsistent. Least squares leaves the set of outputs generated by $A$ unchanged and finds the point in the column space nearest to $\mathbf b$.

Projection onto one direction

For nonzero $\mathbf a$, the projection of $\mathbf b$ onto its span is

$$\operatorname{proj}_{\mathbf a}\mathbf b =\frac{\langle\mathbf b,\mathbf a\rangle} {\langle\mathbf a,\mathbf a\rangle}\mathbf a.$$

The coefficient follows from the orthogonality condition. The residual $\mathbf r=\mathbf b-c\mathbf a$ must satisfy $\langle\mathbf r,\mathbf a\rangle=0$. When $\mathbf a$ has unit norm, the coefficient is simply $\langle\mathbf b,\mathbf a\rangle$.

Projection onto a subspace finds the nearest point

Let $W$ be finite dimensional. Suppose $\widehat{\mathbf b}\in W$ and $\mathbf r=\mathbf b-\widehat{\mathbf b}\in W^\perp$. Every $\mathbf w\in W$ then satisfies

$$\|\mathbf b-\mathbf w\|^2 =\|\mathbf r\|^2+ \|\widehat{\mathbf b}-\mathbf w\|^2.$$

Thus $\widehat{\mathbf b}$ is the unique nearest point. The argument decomposes error into orthogonal directions rather than beginning with differentiation of a distance formula.

If the columns of $Q$ are an orthonormal basis of $W$, then

$$\widehat{\mathbf b}=QQ^{\mathsf T}\mathbf b, \qquad P_W=QQ^{\mathsf T}.$$

The projection matrix satisfies $P_W^2=P_W$ and $P_W^{\mathsf T}=P_W$. One projection already lands in $W$, so a second one changes nothing.

Least squares and the normal equations

Minimizing $\|A\mathbf x-\mathbf b\|^2$ requires $A\widehat{\mathbf x}$ to be the projection of $\mathbf b$ onto $\operatorname{col}(A)$. The residual is orthogonal to every column, so

$$A^{\mathsf T}(\mathbf b-A\widehat{\mathbf x})=\mathbf0.$$

These are the normal equations:

$$A^{\mathsf T}A\widehat{\mathbf x} =A^{\mathsf T}\mathbf b.$$

When the columns of $A$ are independent, $A^{\mathsf T}A$ is invertible and the coefficient vector is unique. With dependent columns, the best predicted output remains unique, but more than one coefficient vector may produce it.

ProofNecessity and uniqueness of coefficients

Suppose $\widehat{\mathbf x}$ minimizes the squared residual, and write $\mathbf r=\mathbf b-A\widehat{\mathbf x}$. Along any coefficient direction $\mathbf h$ the change in error is

$$\|\mathbf r-tA\mathbf h\|^2-\|\mathbf r\|^2 =-2t\mathbf r^{\mathsf T}A\mathbf h+t^2\|A\mathbf h\|^2.$$

If the linear coefficient were nonzero, a sufficiently small $t$ of the appropriate sign would lower the error. Thus $\mathbf r^{\mathsf T}A\mathbf h=0$ for all $\mathbf h$, which is the normal equation. Existence follows from the orthogonal decomposition in the preceding chapter: its component in $\operatorname{col}(A)$ has at least one coefficient preimage.

Finally $\mathbf x^{\mathsf T}A^{\mathsf T}A\mathbf x=\|A\mathbf x\|^2$, so $\ker(A^{\mathsf T}A)=\ker A$. Full column rank makes this kernel zero, hence the square matrix $A^{\mathsf T}A$ invertible. Dependent columns give a nonzero kernel direction and infinitely many minimizing coefficients.

Why the normal equations are sufficient

Let $\widehat{\mathbf x}$ satisfy them and set $\mathbf r=\mathbf b-A\widehat{\mathbf x}$. Every perturbation $\mathbf h$ satisfies

$$\|\mathbf b-A(\widehat{\mathbf x}+\mathbf h)\|^2 =\|\mathbf r\|^2+\|A\mathbf h\|^2.$$

The cross term vanishes because $A^{\mathsf T}\mathbf r=0$. This proves a global minimum, not merely stationarity. Equality holds exactly for $\mathbf h\in\ker A$, so all minimizing coefficients form $\widehat{\mathbf x}+\ker A$. The predicted output is unique even when its coefficients are not.

From interpolation to fitting

Polynomial interpolation requires a curve to pass through every data point. Instead fit $y=\alpha x+\beta$ to $(1,6),(2,7),(3,5)$:

$$A=\begin{pmatrix}1&1\\2&1\\3&1\end{pmatrix}, \qquad \mathbf b=\begin{pmatrix}6\\7\\5\end{pmatrix}.$$

The normal equations are

$$\begin{pmatrix}14&6\\6&3\end{pmatrix} \begin{pmatrix}\alpha\\\beta\end{pmatrix} =\begin{pmatrix}35\\18\end{pmatrix},$$

which give $\alpha=-1/2$ and $\beta=7$. The prediction is $(6.5,6,5.5)^{\mathsf T}$ and the residual is $(-1/2,1,-1/2)^{\mathsf T}$. Direct multiplication verifies $A^{\mathsf T}\mathbf r=\mathbf0$.

QR avoids explicitly forming the normal equations

Gram–Schmidt applied to a full-column-rank matrix gives

$$A=QR,$$

where $Q$ has orthonormal columns and $R$ is upper triangular with nonzero diagonal. The least-squares problem reduces to

$$R\widehat{\mathbf x}=Q^{\mathsf T}\mathbf b.$$

This requires one orthogonalization and one triangular solve. The LU chapter factors a square matrix through elimination, while QR uses orthogonal bases for rectangular systems and least squares.

For the two-norm condition number of a full-column-rank matrix, define $\kappa_2(A)=\sigma_1/\sigma_n$. The SVD construction shows that $A^{\mathsf T}A$ has positive eigenvalues $\sigma_i^2$, so $\kappa_2(A^{\mathsf T}A)=\kappa_2(A)^2$ exactly. Numerical stability of a particular QR implementation is a separate topic; Householder QR and modified Gram–Schmidt belong to a future numerical-linear-algebra treatment.

ProofWhy QR gives this triangular solve

The Gram–Schmidt prefix-span property expresses column $j$ as $\sum_{i\le j}r_{ij}\mathbf q_i$, where $r_{ij}=\mathbf q_i^{\mathsf T}\mathbf a_j$ and $r_{jj}$ is the positive norm of its nonzero remainder. These column identities give $A=QR$ and an invertible upper triangular $R$. Split $\mathbf b=QQ^{\mathsf T}\mathbf b+(I-QQ^{\mathsf T})\mathbf b$ into orthogonal components. Then

$$\|A\mathbf x-\mathbf b\|^2 =\|R\mathbf x-Q^{\mathsf T}\mathbf b\|^2 +\|(I-QQ^{\mathsf T})\mathbf b\|^2.$$

Here $\|Q\mathbf z\|^2=\mathbf z^{\mathsf T}Q^{\mathsf T}Q\mathbf z=\|\mathbf z\|^2$. The second term is fixed and the first attains zero at the stated triangular solve.

Compute the fitting example completely with QR

Use the same three-point design matrix. Normalize its first column to obtain $\mathbf q_1=(1,2,3)^{\mathsf T}/\sqrt{14}$. Removing its component from column two gives

$$\begin{pmatrix}1\\1\\1\end{pmatrix} -\frac{6}{14}\begin{pmatrix}1\\2\\3\end{pmatrix} =\frac17\begin{pmatrix}4\\1\\-2\end{pmatrix}.$$

Thus $\mathbf q_2=(4,1,-2)^{\mathsf T}/\sqrt{21}$ and

$$R=\begin{pmatrix}\sqrt{14}&6/\sqrt{14}\\0&3/\sqrt{21}\end{pmatrix}, \qquad Q^{\mathsf T}\mathbf b= \begin{pmatrix}35/\sqrt{14}\\21/\sqrt{21}\end{pmatrix}.$$

Row two gives $3\beta=21$; row one gives $14\alpha+6\beta=35$. Therefore $\beta=7$ and $\alpha=-1/2$, verifying directly that QR and the normal equations produce the same best prediction.

Exercises

ExerciseProject onto a line

Project $(3,1)$ onto the line spanned by $(1,1)$ and find the residual.

Solution

The coefficient is $4/2=2$, so the projection is $(2,2)$ and the residual is $(1,-1)$. Its inner product with $(1,1)$ is zero.

ExerciseRecognize a projection matrix

For a matrix $Q$ with orthonormal columns, prove that $P=QQ^{\mathsf T}$ satisfies $P^2=P$.

Solution

$P^2=Q(Q^{\mathsf T}Q)Q^{\mathsf T}=QIQ^{\mathsf T}=P$.

ExerciseBest constant fit

Fit a single constant $c$ to data $y_1,\ldots,y_n$ and show that the least-squares solution is the sample mean.

Solution

The design matrix is one column of ones. Its normal equation is $nc=\sum_i y_i$, so $c=\frac1n\sum_i y_i$. The residuals sum to zero.