Orthogonality and Least Squares

Most linear systems that come from real data have no exact solution: there are more equations than unknowns, and the measurements disagree. Orthogonality turns that failure into a well-posed question. Instead of solving $Ax = b$ exactly, we project $b$ onto what $A$ can actually reach and accept the leftover as error.

Orthogonality

Two vectors are orthogonal when their dot product vanishes,

$$u \cdot v = u^{\top} v = 0.$$

Geometrically the angle between them is $90^{\circ}$, and the Pythagorean law holds exactly: $\|u + v\|^2 = \|u\|^2 + \|v\|^2$ precisely when $u \cdot v = 0$. A set of nonzero, mutually orthogonal vectors is automatically independent, which is what makes orthogonal directions such convenient coordinate axes.

Projecting onto a line

Let a line through the origin be spanned by a vector $a$. Any $b$ splits uniquely as

$$b = p + r, \qquad p = \hat{x}\,a \in \text{line}, \qquad r = b - p \perp a.$$

The perpendicularity condition $a \cdot r = 0$ becomes $a \cdot (b - \hat{x} a) = 0$, which we solve for the one scalar $\hat{x}$:

$$\hat{x} = \frac{a \cdot b}{a \cdot a}, \qquad p = \frac{a \cdot b}{a \cdot a}\, a.$$

As a matrix, $b \mapsto p$ is the projection $P = \dfrac{a a^{\top}}{a^{\top} a}$, which satisfies $P^{\top} = P$ and $P^2 = P$ (projecting a second time changes nothing).

Worked example. Project $b = (3, 4)$ onto $a = (1, 1)$. Then $a \cdot b = 3 + 4 = 7$ and $a \cdot a = 1 + 1 = 2$, so

$$\hat{x} = \frac{7}{2} = 3.5, \qquad p = 3.5\,(1, 1) = (3.5,\ 3.5), \qquad r = b - p = (-0.5,\ 0.5).$$

Check the right angle: $r \cdot a = -0.5 + 0.5 = 0$. The residual is perpendicular to the line, as it must be.

Projecting b onto a lineinteractive

line angle θ = 45°

b

(2.10, 0.50)

p

(1.30, 1.30)

r = b − p

(0.80, -0.80)

r · a

-0.000

Drag the point b. Its projection p is the closest point on the line, and the residual r meets the line at a right angle, so r · a stays ~0.

Projecting onto a subspace

Replace the single direction $a$ by the columns of a matrix $A$, taken as a basis for a subspace $S$. Now $p = A\hat{x}$, and the residual $r = b - A\hat{x}$ must be orthogonal to every column at once, i.e. $A^{\top} r = 0$:

$$A^{\top}(b - A\hat{x}) = 0 \;\Longrightarrow\; A^{\top} A\, \hat{x} = A^{\top} b.$$

When $A$ has independent columns, $A^{\top}A$ is invertible, so

$$\hat{x} = (A^{\top} A)^{-1} A^{\top} b, \qquad p = A(A^{\top} A)^{-1} A^{\top} b = P b.$$

The line formula is just the $1$-column case: $A = a$ makes $A^{\top}A = a \cdot a$ a scalar.

Least squares and the normal equations

When $Ax = b$ has no solution, $b$ lies outside the column space of $A$. The least-squares choice is the $\hat{x}$ that minimizes the squared error

$$\|A x - b\|^2.$$

Setting its gradient to zero reproduces exactly the same normal equations,

$$A^{\top} A\, \hat{x} = A^{\top} b.$$

This is no coincidence: the minimizer makes the residual $r = b - A\hat{x}$ orthogonal to the column space, so $p = A\hat{x}$ is the closest point of $S$ to $b$. Any other point in $S$ adds a component along the subspace, which by Pythagoras only lengthens $r$.

Worked example. Take

$$A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 0 \end{bmatrix}, \qquad b = \begin{bmatrix} 2 \\ 4 \\ 0 \end{bmatrix}.$$

The columns are orthogonal, so $A^{\top}A$ is diagonal:

$$A^{\top} A = \begin{bmatrix} 3 & 0 \\ 0 & 2 \end{bmatrix}, \qquad A^{\top} b = \begin{bmatrix} 6 \\ -2 \end{bmatrix}, \qquad \hat{x} = \begin{bmatrix} 2 \\ -1 \end{bmatrix}.$$

Then $p = A\hat{x} = (1, 3, 2)$ and $r = b - p = (1, 1, -2)$. Both columns are orthogonal to the residual: $r \cdot (1,1,1) = 0$ and $r \cdot (1,-1,0) = 0$, which confirms $p$ is the projection.

Orthonormal bases: Gram-Schmidt and QR

The algebra collapses when the basis is orthonormal, since then $A^{\top}A = I$. Gram-Schmidt builds such a basis from any independent set by subtracting off the projection onto the directions already chosen, then normalizing. Collecting the results as the columns of $Q$ (with $Q^{\top} Q = I$) and the coefficients in an upper-triangular $R$ gives the factorization $A = QR$. The normal equations then reduce to $R\hat{x} = Q^{\top} b$, solved by back-substitution with no matrix inverse and far better numerical behavior.¹

Footnotes

1. Strang, Introduction to Linear Algebra (5th ed., 2016). ↩