Orthogonality is where linear algebra becomes a tool for data. When an exact solution to \(\mA\vx=\vb\) does not exist — the everyday situation with real, noisy, over-determined data — orthogonality tells us how to find the best approximate solution. This chapter builds projections, the normal equations of least squares, the Gram–Schmidt process, and the QR factorization: the machinery directly behind linear regression.

Orthogonal and orthonormal sets

A set of vectors is orthogonal if every pair has zero dot product, and orthonormal if in addition each is a unit vector. A square matrix \(\mQ\) whose columns are orthonormal satisfies \(\mQ\tp\mQ=\mI\) and is called an orthogonal matrix; it preserves lengths and angles (\(\norm{\mQ\vx}=\norm{\vx}\)).

Orthonormal bases are the best coordinate systems in existence. In one, computing a vector’s coordinates is just taking dot products (\(x_i=\vq_i\tp\vx\)), there is no distortion of length or angle, and the inverse of the basis matrix is simply its transpose. Numerically they never amplify error. Much of advanced linear algebra is an effort to manufacture orthonormal bases (Gram–Schmidt, QR, eigenvectors of symmetric matrices, the SVD).

Orthogonal complements

The orthogonal complement \(W^\perp\) of a subspace \(W\) is the set of all vectors orthogonal to everything in \(W\). The Fundamental Theorem (Chapter [ch:vectorspaces]) said it already: row space and null space are orthogonal complements in \(\R^n\); column space and left null space are orthogonal complements in \(\R^m\). Any vector splits uniquely into a part in \(W\) and a part in \(W^\perp\).

Projection onto a subspace

Generalizing the projection-onto-a-line from Chapter [ch:vectors]: given a subspace spanned by the columns of \(\mA\), the projection of \(\vb\) onto that column space is the closest point in it.

If \(\mA\) has independent columns, the orthogonal projection of \(\vb\) onto \(\col(\mA)\) is \[\hat\vb = \mA(\mA\tp\mA)\inv\mA\tp\,\vb = \mP\vb,\qquad \mP=\mA(\mA\tp\mA)\inv\mA\tp.\] The projection matrix \(\mP\) satisfies \(\mP\tp=\mP\) and \(\mP^2=\mP\) (projecting twice changes nothing), and the residual \(\vb-\hat\vb\) is orthogonal to \(\col(\mA)\).

Least squares: the normal equations

When \(\mA\vx=\vb\) has no solution (more equations than unknowns, \(\vb\notin\col(\mA)\)), we instead minimize the squared error \(\norm{\mA\vx-\vb}_2^2\). The minimizer makes the residual orthogonal to the column space, which gives the celebrated normal equations.

The vector \(\hat\vx\) minimizing \(\norm{\mA\vx-\vb}_2^2\) solves \[\boxed{\ \mA\tp\mA\,\hat\vx = \mA\tp\vb\ }\qquad\Longrightarrow\qquad \hat\vx=(\mA\tp\mA)\inv\mA\tp\vb\] (the last step assuming \(\mA\) has independent columns). The fitted values are \(\hat\vb=\mA\hat\vx=\mP\vb\).

Fitting a linear model is projection. The achievable predictions form the column space of the design matrix; the targets \(\vb\) usually lie outside it; least squares drops a perpendicular onto that subspace. The orthogonality of the residual is not a trick — it is the geometric definition of “best fit.” This single picture is the foundation of linear regression, and via the pseudoinverse (Chapter [ch:svd]) of much more.

To fit \(y=c+dx\) through points \((x_i,y_i)\), set \(\mA=\begin{bsmallmatrix}1&x_1\\ \vdots&\vdots\\ 1&x_m\end{bsmallmatrix}\), \(\vb=\begin{bsmallmatrix}y_1\\ \vdots\\ y_m\end{bsmallmatrix}\), and solve \(\mA\tp\mA\,\hat\vx=\mA\tp\vb\). The \(2\times2\) system encodes the familiar slope/intercept formulas of statistics — here derived purely geometrically.

Forming and solving \(\mA\tp\mA\) directly (the textbook normal equations) squares the condition number of \(\mA\), losing up to twice as many digits of precision. With nearly-collinear features this is numerically dangerous. Production solvers therefore fit least squares via QR or SVD of \(\mA\) directly — never by inverting \(\mA\tp\mA\). Use , not .

Gram–Schmidt and the QR factorization

Given independent (but not orthogonal) vectors, the Gram–Schmidt process manufactures an orthonormal basis for the same span: take each vector, subtract its projections onto the directions already fixed, and normalize.

Applying Gram–Schmidt to the columns of \(\mA\) yields the QR factorization \[\mA = \mQ\mR,\] where \(\mQ\) has orthonormal columns (\(\mQ\tp\mQ=\mI\)) spanning \(\col(\mA)\) and \(\mR\) is upper-triangular. Least squares then reduces to the well-conditioned triangular solve \(\mR\hat\vx=\mQ\tp\vb\).

QR is “orthogonalize the columns and remember how.” Because \(\mQ\) is perfectly conditioned, QR is the numerically stable way to solve least-squares problems and a building block of eigenvalue algorithms (the QR algorithm). In practice the modified Gram–Schmidt or Householder reflections are used for stability.

Least squares is linear regression, and the projection view explains regularization geometrically. Orthogonality also underlies whitening/decorrelation of features, orthogonal weight initialization (which preserves signal norms across deep layers and combats vanishing/exploding gradients), and the orthonormal bases that make PCA and the SVD numerically trustworthy. When you call a regression or PCA routine, QR or SVD is almost certainly running underneath.

import numpy as np
A = np.c_[np.ones(50), np.linspace(0,5,50)]      # design matrix (1, x)
b = 2.0 + 1.5*A[:,1] + 0.3*np.random.randn(50)   # noisy line
x_hat, *_ = np.linalg.lstsq(A, b, rcond=None)    # stable least squares
Q, R = np.linalg.qr(A)
x_qr = np.linalg.solve(R, Q.T @ b)               # same answer via QR
print(x_hat, x_qr)

Chapter summary

  • Orthonormal sets are the ideal coordinates: coordinates by dot products, inverse by transpose, no distortion.

  • Projection onto \(\col(\mA)\) is \(\mP\vb=\mA(\mA\tp\mA)\inv\mA\tp\vb\); the residual is orthogonal to the subspace.

  • Least squares solves \(\mA\tp\mA\hat\vx=\mA\tp\vb\): best fit \(=\) projection. This is linear regression.

  • Gram–Schmidt \(\to\) QR; fit least squares via QR/SVD, never by inverting \(\mA\tp\mA\).