Chapter 12: Orthogonality, Projections & Least Squares

Chapter 12: Orthogonality, Projections & Least Squares

AI Reading

Quick summary of this article

Preparing the AI summary…

AI Mathematics Masterclass — Chapter 12 of 48

When a linear system has no exact solution, the right question is not “how do I force one” but “which point in the reachable set is closest to what I want”. That question is answered by orthogonal projection, and its application to over-determined systems is least squares — the closed-form solution to linear regression. This chapter derives the projection formula, shows why the normal equations produce it, explains when AᵀA is singular, and presents QR as the numerically stable route that practitioners should actually take.

1. Technical Audit & Core Learning Objectives

Component Common Tutorial Deficiency Engineering Standard Applied Here
Orthogonality Defined as “dot product zero” with no consequence drawn. Linked to independence, cheap inversion, and the residual condition.
Projection Formula given without derivation. Derived from the orthogonality of the residual.
Normal equations Presented as magic, with no warning about AᵀA‘s conditioning. Derived geometrically; the conditioning penalty κ(A)² stated and demonstrated.
Numerics inv(XᵀX)Xᵀy taught as the method. Explicitly discouraged; QR and lstsq shown as the correct routes.

Core learning objectives. After this chapter you should be able to:

  1. Test two vectors for orthogonality and build an orthonormal set.
  2. Derive and apply the projection formula p = (a·b / a·a)·a.
  3. Show that the residual b − p is orthogonal to the subspace.
  4. Derive the normal equations AᵀAŵ = Aᵀy from that condition.
  5. Explain why AᵀA can be singular and what to use instead.
  6. Perform Gram–Schmidt and state why QR is preferred numerically.

2. Orthogonality

Two perpendicular vectors with the right-angle marker and zero dot product
Figure 12.1: Perpendicular vectors have zero dot product — no component of one lies along the other.
u ⊥ v   ⇔   u · v = 0

Orthonormal:  u·v = 0   and   ‖u‖ = ‖v‖ = 1
For an orthonormal matrix Q:  QᵀQ = I  ⇒  Q⁻¹ = Qᵀ

Orthogonal vectors are automatically linearly independent — if a combination Σcᵢqᵢ = 0, dotting with qⱼ isolates cⱼ‖qⱼ‖² = 0, so every coefficient is zero. That is why orthogonal bases make coordinate extraction trivial: you project instead of solving.

import numpy as np

u = np.array([1.0, 0.0, 0.0])
v = np.array([0.0, 3.0, 0.0])
print("u . v =", u @ v)                       # 0.0

Q = np.array([[0.0, -1.0], [1.0, 0.0]])       # 90-degree rotation
print("Q.T @ Q =\n", Q.T @ Q)
assert np.allclose(Q.T @ Q, np.eye(2))
print("inverse is the transpose:", np.allclose(np.linalg.inv(Q), Q.T))

3. Projection Onto a Vector

Vector b projected onto vector a with the perpendicular residual shown explicitly
Figure 12.2: The projection is the point on the line closest to b, and the residual is perpendicular to it.

The projection of b onto a is the point on the line through a that is closest to b. “Closest” means the residual e = b − p is perpendicular to a — that condition defines the projection and yields the formula.

p = t·a                 p must lie on the line through a
e = b − p               the residual
e · a = 0               perpendicularity condition

(b − t·a) · a = 0
b·a − t(a·a) = 0
t = (a·b) / (a·a)

p = [(a·b) / (a·a)] · a
import numpy as np

a = np.array([5.0, 0.0])
b = np.array([2.0, 3.0])

t = (a @ b) / (a @ a)
p = t * a
e = b - p
print("t      :", t)                  # 0.4
print("p      :", p)                  # [2. 0.]
print("e      :", e)                  # [0. 3.]
print("e . a  :", e @ a)              # 0.0  -> orthogonal
assert np.isclose(e @ a, 0.0)

4. Least Squares

Scatter plot with a fitted regression line and vertical residual segments drawn
Figure 12.3: Least squares fits the line that minimises the sum of squared vertical residuals.

With more equations than unknowns the system is inconsistent: y is not in the column space of X, so there is no exact w. Instead you choose the ŵ whose prediction Xŵ is the projection of y onto that column space.

import numpy as np

rng = np.random.default_rng(7)
x = np.linspace(0, 5, 12)
y = 1.8 * x + 0.9 + rng.normal(0, 0.6, size=x.size)

X = np.column_stack([x, np.ones_like(x)])       # design matrix with intercept column
w, *_ = np.linalg.lstsq(X, y, rcond=None)
print("lstsq slope, intercept:", np.round(w, 4))

# compare against the closed form
w_closed = np.linalg.solve(X.T @ X, X.T @ y)
print("normal-eq solution     :", np.round(w_closed, 4))
assert np.allclose(w, w_closed, atol=1e-9)

pred = X @ w
resid = y - pred
print("residual is orthogonal to every column:")
print("  X0 . e =", round(X[:, 0] @ resid, 10))
print("  X1 . e =", round(X[:, 1] @ resid, 10))

The orthogonality prints are the real content. Least squares is not “the line that looks right” — it is the unique line whose residual vector is perpendicular to the design matrix’s column space. Everything else follows.

5. The Normal Equations

Vector y outside a plane representing the column space, with its projection onto the plane and perpendicular residual
Figure 12.4: The projection geometry behind the normal equations. The residual is perpendicular to the whole plane.
Require  Xᵀ(y − Xŵ) = 0        residual orthogonal to every column
⇒        Xᵀy − XᵀXŵ = 0
⇒        XᵀX ŵ = Xᵀy            the normal equations

If XᵀX is invertible:  ŵ = (XᵀX)⁻¹Xᵀy
Situation What Happens Remedy
Full rank X Unique solution exists Use QR or lstsq
Collinear columns XᵀX singular, infinite solutions Drop a column, or add ridge λI
Nearly collinear κ(XᵀX) = κ(X)² — precision halves QR avoids squaring the condition number
import numpy as np

# duplicated feature column -> singular XtX
X = np.array([[1.0, 1.0, 1.0],
              [2.0, 2.0, 1.0],
              [3.0, 3.0, 1.0]])
y = np.array([1.0, 2.0, 3.5])

print("rank X   :", np.linalg.matrix_rank(X))          # 2 of 3 columns
print("det XtX  :", round(np.linalg.det(X.T @ X), 12)) # 0.0

w, *_ = np.linalg.lstsq(X, y, rcond=None)              # still works
print("min-norm w:", np.round(w, 4))
print("first two weights are identical:", np.isclose(w[0], w[1]))

6. Gram–Schmidt and QR

Four steps of Gram-Schmidt orthogonalisation and the QR relation
Figure 12.5: Gram–Schmidt builds an orthonormal basis one vector at a time. QR is the packaged form.
import numpy as np

def gram_schmidt(V):
    """Return an orthonormal basis for the columns of V."""
    Q = []
    for v in V.T:
        w = v.astype(float).copy()
        for q in Q:
            w = w - (q @ w) * q
        norm = np.linalg.norm(w)
        if norm < 1e-12:
            raise ValueError("columns are linearly dependent")
        Q.append(w / norm)
    return np.column_stack(Q)

V = np.array([[1.0, 1.0, 0.0],
              [1.0, 0.0, 1.0],
              [0.0, 1.0, 1.0]])
Q = gram_schmidt(V)
print("Q:\n", np.round(Q, 4))
print("QᵀQ ≈ I:", np.allclose(Q.T @ Q, np.eye(Q.shape[1])))
assert np.allclose(Q.T @ Q, np.eye(Q.shape[1]))

Gram–Schmidt as written is numerically fragile: repeated subtraction accumulates error when the inputs are nearly parallel. Production code uses Householder reflections (np.linalg.qr), which produce the same Q without that instability. The reason to care is that least squares via QR never forms XᵀX, so it never squares the condition number.

7. Worked Examples

7.1 Projection and residual

project (3,4) onto (1,0):
t = 3/1 = 3,  p = (3,0),  e = (0,4),  e·a = 0 ✓

7.2 Orthonormalise two vectors

v₁ = (3,4)  →  q₁ = (0.6, 0.8)
v₂ = (1,0)  →  v₂ − (v₂·q₁)q₁ = (1,0) − 0.6(0.6,0.8) = (0.64, −0.48)
               normalise → (0.8, −0.6)
q₁·q₂ = 0.48 − 0.48 = 0 ✓   both unit length ✓

7.3 Fit a line through three points

points (0,1), (1,2), (2,4)
design X = [[0,1],[1,1],[2,1]],  y = [1,2,4]
XᵀX = [[5,3],[3,3]],  Xᵀy = [10,7]
ŵ = (XᵀX)⁻¹ Xᵀy ≈ (1.5, 0.833)
line: ŷ = 1.5x + 0.833

7.4 Why not invert

If κ(X) = 10³, then κ(XᵀX) = 10⁶.
Double precision has ~16 digits, so ~10 survive — an order of
magnitude of accuracy lost purely from how you chose to compute.

7.5 Ridge as conditioning

(XᵀX + λI) ŵ = Xᵀy
Adding λI makes every eigenvalue at least λ, so the matrix is
always invertible. That is Ridge regression, and its purpose is
partly numeric, not only statistical.

8. Verify It in Python

import numpy as np

# --- 1. orthogonality and free inverse ----------------------------
Q = np.array([[0.0, -1.0], [1.0, 0.0]])
assert np.allclose(Q.T @ Q, np.eye(2))
assert np.allclose(np.linalg.inv(Q), Q.T)
print("orthogonal matrix: Q^-1 == Q.T")

# --- 2. projection formula and residual ---------------------------
a, b = np.array([5., 0.]), np.array([2., 3.])
p = ((a @ b) / (a @ a)) * a
assert np.allclose(p, [2., 0.])
assert np.isclose((b - p) @ a, 0.0)
print("projection:", p, " residual orthogonal")

# --- 3. projection is the closest point on the line ---------------
grid = np.linspace(-5, 10, 4001)
pts = np.array([[t * a[0], t * a[1]] for t in grid])
dists = np.linalg.norm(pts - b, axis=1)
closest = pts[np.argmin(dists)]
assert np.allclose(closest, p, atol=1e-2)
print("projection minimises distance: ", np.round(closest, 3))

# --- 4. normal equations agree with lstsq -------------------------
rng = np.random.default_rng(3)
x = np.linspace(0, 4, 10)
y = 2.5 * x - 1.0 + rng.normal(0, 0.3, x.size)
X = np.column_stack([x, np.ones_like(x)])

w_ls, *_ = np.linalg.lstsq(X, y, rcond=None)
w_ne = np.linalg.solve(X.T @ X, X.T @ y)
assert np.allclose(w_ls, w_ne, atol=1e-9)
print("lstsq == normal equations:", np.round(w_ls, 4))

# --- 5. residual orthogonal to column space -----------------------
e = y - X @ w_ls
assert np.allclose(X.T @ e, 0.0, atol=1e-9)
print("X^T e ~ 0:", np.round(X.T @ e, 12))

# --- 6. QR beats normal equations on a bad matrix -----------------
bad = np.array([[1.0, 1.0], [1.0, 1.0 + 1e-8]])
print("kappa(X)   :", f"{np.linalg.cond(bad):.3e}")
print("kappa(XtX) :", f"{np.linalg.cond(bad.T @ bad):.3e}")
assert np.linalg.cond(bad.T @ bad) > 1e10
Qm, Rm = np.linalg.qr(bad)
assert np.allclose(Qm @ Rm, bad)
print("QR reconstruction exact")

# --- 7. Gram-Schmidt yields an orthonormal basis ------------------
def gs(V):
    out = []
    for v in V.T:
        w = v.astype(float).copy()
        for q in out:
            w -= (q @ w) * q
        out.append(w / np.linalg.norm(w))
    return np.column_stack(out)

V = np.array([[1., 1., 0.], [1., 0., 1.], [0., 1., 1.]])
G = gs(V)
assert np.allclose(G.T @ G, np.eye(3))
print("Gram-Schmidt orthonormal:", np.allclose(G.T @ G, np.eye(3)))

# --- 8. ridge makes an otherwise singular system solvable ---------
lam = 1e-3
rhs = bad.T @ np.array([1.0, 2.0])
w_ridge = np.linalg.solve(bad.T @ bad + lam * np.eye(2), rhs)
assert np.all(np.isfinite(w_ridge))
print("ridge solution:", np.round(w_ridge, 4))
print("all assertions passed")

9. Practice Questions

  1. Test (1,2,2) and (2,−2,1) for orthogonality.
  2. Project (3,4) onto (1,0); give p and e and verify e ⊥ a.
  3. Project (1,1) onto the line spanned by (1,1) — what happens and why?
  4. Derive t = (a·b)/(a·a) from the orthogonality condition.
  5. Write the normal equations and state the invertibility condition.
  6. What is κ(XᵀX) in terms of κ(X), and why does it matter?
  7. Show that Xᵀe = 0 at the least-squares solution.
  8. Orthonormalise (1,0,0) and (1,1,0).
  9. Why does ridge regularisation make the system solvable?
  10. Why is QR preferred over the normal equations for least squares?

Leave a Reply

Your email address will not be published. Required fields are marked *