Least squares — normal equations, QR approach: Exercises

Quick reminder of the two master equations you will use constantly:

Level 1 — Recognition

Problem 1.1

Which of these systems $A x = b$ needs least squares (no exact solution guaranteed), and which is an ordinary square solve? State why.

(a) $A$ is $5 \times 2$ . (b) $A$ is $3 \times 3$ invertible. (c) $A$ is $4 \times 4$ but rank $2$ .

Recall Solution

What decides it: least squares is for tall systems — more equations than unknowns — where $b$ may not lie in the column space.

(a) $5 \times 2$ : tall ( $m = 5 > n = 2$ ). Overdetermined → use least squares.
(b) $3 \times 3$ invertible: square with an inverse → ordinary solve $x = A^{- 1} b$ , exact.
(c) $4 \times 4$ rank $2$ : square but rank-deficient (columns dependent). No unique inverse; least squares still applies but $\hat{x}$ is not unique — you'd reach for the Pseudoinverse (Moore-Penrose). So: least squares in the generalised sense, minimum-norm solution.

Problem 1.2

Write down, without deriving, the normal equations and the projection matrix $P$ onto $Col (A)$ for a full-column-rank $A$ .

Recall Solution

Normal equations: $A^{⊤} A \hat{x} = A^{⊤} b$ . Explicit solution: $\hat{x} = (A^{⊤} A)^{- 1} A^{⊤} b$ . Projection matrix: $P = A (A^{⊤} A)^{- 1} A^{⊤}$ , satisfying $P^{2} = P$ (projecting twice = projecting once) and $P^{⊤} = P$ (symmetric).

Level 2 — Application

Problem 2.1

Fit the best horizontal line $y = c$ (a constant, no slope) to the data $y$ -values $4, 2, 3$ . Find $\overset{c}{^}$ using the normal equations.

Recall Solution

Set up. Predicting each point by the single constant $c$ means $A x = b$ with a single column of ones: $A = 111, b = 423, x = (c) .$ Compute. $A^{⊤} A = 1^{2} + 1^{2} + 1^{2} = 3$ , and $A^{⊤} b = 4 + 2 + 3 = 9$ . Solve. $3 c = 9 \Rightarrow \overset{c}{^} = 3$ . Meaning: the best constant fit is just the average of the data — least squares with a column of ones is the mean. That's the simplest Linear Regression there is.

Problem 2.2

Fit $y = c + d t$ to points $(1, 1), (2, 2), (3, 2)$ . Find $\overset{c}{^}, \hat{d}$ .

Recall Solution

Set up. Row $i$ says $c + d t_{i} = y_{i}$ : $A = 111123, b = 122 .$ Compute $A^{⊤} A$ (entries are dot products of columns $1 = (1, 1, 1)$ and $t = (1, 2, 3)$ ): $A^{⊤} A = (1 \cdot 1 t \cdot 1 1 \cdot t t \cdot t) = (36614), A^{⊤} b = (1 + 2 + 2 1 + 4 + 6) = (511) .$ Solve $(36614) (d c) = (11 5)$ . Subtract $2 \times$ (row 1) from row 2: $(14 - 12) d = 11 - 10 \Rightarrow 2 d = 1 \Rightarrow \hat{d} = \frac{1}{2}$ . Then $3 c + 6 (\frac{1}{2}) = 5 \Rightarrow 3 c = 2 \Rightarrow \overset{c}{^} = \frac{2}{3}$ . Best line: $y = \frac{2}{3} + \frac{1}{2} t$ . See the figure — the miss-arrows point straight up/down from the line.

Figure — Least squares — normal equations, QR approach

Level 3 — Analysis

Problem 3.1

For Problem 2.2, compute the residual $r = b - A \hat{x}$ and verify $A^{⊤} r = 0$ . Explain geometrically what $A^{⊤} r = 0$ says.

Recall Solution

Predictions $\hat{b} = A \hat{x}$ with $c = \frac{2}{3}, d = \frac{1}{2}$ : $\hat{b}_{1} = \frac{2}{3} + \frac{1}{2} (1) = \frac{7}{6}, \hat{b}_{2} = \frac{2}{3} + \frac{1}{2} (2) = \frac{5}{3}, \hat{b}_{3} = \frac{2}{3} + \frac{1}{2} (3) = \frac{13}{6} .$ Residual $r = b - \hat{b}$ : $r_{1} = 1 - \frac{7}{6} = - \frac{1}{6}, r_{2} = 2 - \frac{5}{3} = \frac{1}{3}, r_{3} = 2 - \frac{13}{6} = - \frac{1}{6} .$ Check orthogonality: $1 \cdot r = - \frac{1}{6} + \frac{1}{3} - \frac{1}{6} = 0, t \cdot r = 1 (- \frac{1}{6}) + 2 (\frac{1}{3}) + 3 (- \frac{1}{6}) = - \frac{1}{6} + \frac{2}{3} - \frac{1}{2} = 0.$ Both zero, so $A^{⊤} r = 0$ . ✓ Geometry: the residual arrow is perpendicular to every column of $A$ , hence perpendicular to the whole plane $Col (A)$ . That's the Orthogonal Projection condition — $\hat{b}$ is the shadow of $b$ on that plane, and $r$ is the straight-out gap.

Problem 3.2

The condition number $κ$ measures how much a matrix amplifies input errors. Given a matrix with $κ (A) = 1 0^{4}$ , compare the error-amplification of solving via normal equations vs QR. Which do you trust and why?

Recall Solution

Key fact: forming $A^{⊤} A$ squares the condition number: $κ (A^{⊤} A) = κ (A)^{2}$ .

Normal equations solve a system governed by $κ (A^{⊤} A) = (1 0^{4})^{2} = 1 0^{8}$ .
QR works directly with $R$ , whose conditioning matches $κ (A) = 1 0^{4}$ .

In digits: double precision carries about $16$ significant digits. Losing $lo g_{10} (1 0^{8}) = 8$ digits (normal equations) leaves $\approx 8$ good digits; losing $lo g_{10} (1 0^{4}) = 4$ digits (QR) leaves $\approx 12$ . Trust QR — it never forms $A^{⊤} A$ , so it avoids the squaring. See Condition Number and QR Factorization.

Level 4 — Synthesis

Problem 4.1

Solve Problem 2.2 again, but this time by QR. Build $Q, R$ by Gram-Schmidt Process on the columns $a_{1} = (1, 1, 1), a_{2} = (1, 2, 3)$ , then solve $R \hat{x} = Q^{⊤} b$ . Confirm you get $\overset{c}{^} = \frac{2}{3}, \hat{d} = \frac{1}{2}$ .

Recall Solution

Step 1 — normalise the first column. $∥ a_{1} ∥ = 1 + 1 + 1 = 3$ , so $q_{1} = \frac{1}{3} (1, 1, 1) .$ Step 2 — remove $a_{2}$ 's shadow along $q_{1}$ . The overlap is $q_{1}^{⊤} a_{2} = \frac{1}{3} (1 + 2 + 3) = \frac{6}{3} = 23$ . Subtract: $a_{2} - (23) q_{1} = (1, 2, 3) - 23 \cdot \frac{1}{3} (1, 1, 1) = (1, 2, 3) - (2, 2, 2) = (- 1, 0, 1) .$ Its length is $1 + 0 + 1 = 2$ , so $q_{2} = \frac{1}{2} (- 1, 0, 1)$ . Step 3 — read off $R = Q^{⊤} A$ (upper triangular by construction): $R = (∥ a_{1} ∥ 0 q_{1}^{⊤} a_{2} ∥ (- 1, 0, 1) ∥) = (30232) .$ Step 4 — compute $Q^{⊤} b$ with $b = (1, 2, 2)$ : $q_{1}^{⊤} b = \frac{1}{3} (1 + 2 + 2) = \frac{5}{3}, q_{2}^{⊤} b = \frac{1}{2} (- 1 + 0 + 2) = \frac{1}{2} .$ Step 5 — back-substitute $R \hat{x} = Q^{⊤} b$ . Bottom row first: $2 \hat{d} = \frac{1}{2} \Rightarrow \hat{d} = \frac{1}{2} .$ Top row: $3 \overset{c}{^} + 23 (\frac{1}{2}) = \frac{5}{3}$ , i.e. $3 \overset{c}{^} = \frac{5}{3} - 3 = \frac{5 - 3}{3} = \frac{2}{3}$ , so $\overset{c}{^} = \frac{2}{3}$ . Same answer $\overset{c}{^} = \frac{2}{3}, \hat{d} = \frac{1}{2}$ — no $A^{⊤} A$ was ever formed. ✓

Problem 4.2

Show algebraically that $R \hat{x} = Q^{⊤} b$ is the same equation as the normal equations when $A = QR$ and $R$ is invertible.

Recall Solution

Start from the normal equations and substitute $A = QR$ : $(QR)^{⊤} (QR) \hat{x} = (QR)^{⊤} b .$ Transpose of a product reverses order: $(QR)^{⊤} = R^{⊤} Q^{⊤}$ . So the left side is $R^{⊤} Q^{⊤} QR \hat{x}$ . Because $Q$ has orthonormal columns, $Q^{⊤} Q = I$ (the identity), which drops out: $R^{⊤} R \hat{x} = R^{⊤} Q^{⊤} b .$ $R$ is invertible (full rank), so $R^{⊤}$ is invertible; multiply both sides on the left by $(R^{⊤})^{- 1}$ : $R \hat{x} = Q^{⊤} b .$ They are algebraically identical — QR is just a numerically safer road to the same $\hat{x}$ .

Level 5 — Mastery

Problem 5.1

A rank-deficient case. Let $A = 111222, b = 102 .$ (a) Show $A^{⊤} A$ is not invertible. (b) Explain what goes wrong with $\hat{x} = (A^{⊤} A)^{- 1} A^{⊤} b$ . (c) Find the projection $\hat{b} = A \hat{x}$ anyway — it is still unique — and give the minimum-norm $\hat{x}$ .

Recall Solution

(a) Column 2 is exactly $2 \times$ column 1, so rank $= 1$ (columns dependent). Compute: $A^{⊤} A = (36612), det = 3 \cdot 12 - 6 \cdot 6 = 36 - 36 = 0.$ Zero determinant ⇒ not invertible. (b) $(A^{⊤} A)^{- 1}$ does not exist, so the formula is meaningless; the normal equations have infinitely many solutions $\hat{x}$ (a whole line of them), because any shift along the dependency direction $(2, - 1)$ leaves $A \hat{x}$ unchanged. (c) The column space is the single direction $u = (1, 1, 1)$ (since both columns are multiples of it). Project $b$ onto $u$ : $\hat{b} = \frac{u ^{⊤} b}{u ^{⊤} u} u = \frac{1 + 0 + 2}{3} (1, 1, 1) = 1 \cdot (1, 1, 1) = (1, 1, 1) .$ This projection is unique even though $\hat{x}$ is not. To pick one $\hat{x}$ : any $(c, d)$ with $c + 2 d = 1$ works. The minimum-norm choice (via Pseudoinverse (Moore-Penrose)) minimises $c^{2} + d^{2}$ subject to $c + 2 d = 1$ ; using $\hat{x} = \frac{1}{5} (1, 2)$ gives $c = \frac{1}{5}, d = \frac{2}{5}$ , and indeed $\frac{1}{5} + 2 \cdot \frac{2}{5} = \frac{1}{5} + \frac{4}{5} = 1$ . ✓

Problem 5.2

Weighted least squares. Suppose measurement 2 is twice as reliable as measurements 1 and 3, so you weight the residuals by $w = (1, 2, 1)$ and minimise $\sum_{i} w_{i}^{2} r_{i}^{2}$ . Show this is ordinary least squares on $W A$ and $W b$ where $W = diag (1, 2, 1)$ , and write the modified normal equations.

Recall Solution

Rewrite the objective. With $r = b - A x$ , $\sum_{i} w_{i}^{2} r_{i}^{2} = ∥ W (b - A x) ∥^{2} = ∥ W b - W A x ∥^{2},$ because $W = diag (1, 2, 1)$ scales each component and $∥ \cdot ∥^{2}$ sums the squares. This is exactly ordinary least squares with data matrix $\tilde{A} = W A$ and target $\tilde{b} = W b$ . Apply the normal equations to $\tilde{A}, \tilde{b}$ : $\tilde{A}^{⊤} \tilde{A} \hat{x} = \tilde{A}^{⊤} \tilde{b} ⟹ (W A)^{⊤} (W A) \hat{x} = (W A)^{⊤} W b .$ Since $W$ is diagonal (symmetric), $(W A)^{⊤} = A^{⊤} W$ , so with $W^{⊤} W = W^{2} = diag (1, 4, 1)$ : $A^{⊤} W^{2} A \hat{x} = A^{⊤} W^{2} b .$ Meaning: trustworthy points ( $w_{2} = 2$ , so $w_{2}^{2} = 4$ ) pull the fit toward themselves four times harder. This is the bridge to weighted Linear Regression.

Recall One-line self-check for the whole page

Can you, from memory, (1) set up $A, b$ for a line fit, (2) solve via normal equations, (3) solve the same problem via QR, (4) verify $A^{⊤} r = 0$ , and (5) explain why QR beats normal equations on conditioning? If yes for all five, you own this topic.