Orthogonality & Least Squares

The coefficient is chosen to make the leftover perpendicular: $(\mathbf u - c\mathbf v)\cdot\mathbf v = 0$ forces $c = \tfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}$. For $\mathbf u = (1, 3)$ and $\mathbf v = (3, 1)$: $c = \tfrac{3 + 3}{9 + 1} = \tfrac35$, the shadow is $\tfrac35(3, 1) = (\tfrac95, \tfrac35)$, and the leftover $(-\tfrac45, \tfrac{12}{5})$ has dot product $-\tfrac{12}{5} + \tfrac{12}{5} = 0$ with $\mathbf v$. Replacing $\mathbf v$ by any nonzero multiple gives the same shadow: $\mathbf v$ appears twice on top and twice below, so the scale cancels.

Why the normal equations: the vectors $A\mathbf x$ fill the column space of $A$, and the closest of them to $\mathbf b$ is the one whose error $\mathbf b - A\hat{\mathbf x}$ is perpendicular to that whole space — the projection idea again, one dimension up. Perpendicular to every column means $A^{\mathsf T}(\mathbf b - A\hat{\mathbf x}) = \mathbf 0$, which rearranges to $A^{\mathsf T}A\hat{\mathbf x} = A^{\mathsf T}\mathbf b$. If $A$ has independent columns, $A^{\mathsf T}A$ is invertible and the best fit is unique.

In matrix form this is $A = (1, 1, 1)^{\mathsf T}$ and $\mathbf b = (1, 3, 5)$: one column, all ones. The normal equation reads $3c = 1 + 3 + 5 = 9$, so $c = 3$ again. The errors $1 - 3, 3 - 3, 5 - 3$, that is $-2, 0, 2$, add to zero — the error vector $(-2, 0, 2)$ is perpendicular to the column $(1, 1, 1)$. The total squared error is $4 + 0 + 4 = 8$, and no other constant does better.

Orthogonality makes the pieces independent. To check that $\mathbf b - \mathbf p$ is perpendicular to $\mathbf u_1$, dot it with $\mathbf u_1$: every term with $\mathbf u_j$, $j \ne 1$, vanishes, and the $\mathbf u_1$ term was built to cancel $\mathbf b\cdot\mathbf u_1$. So each coefficient can be found alone, with one dot product, instead of solving a system. Gram–Schmidt works for the same reason: subtracting the projections leaves exactly the part of the new vector perpendicular to everything before it, and the span never changes along the way.

Subtract it: $\mathbf u_2 = (1, 0, 1) - \tfrac12(1, 1, 0) = \left(\tfrac12, -\tfrac12, 1\right)$. Check: $\mathbf u_1\cdot\mathbf u_2 = \tfrac12 - \tfrac12 + 0 = 0$ ✓. Clearing the fraction, $(1, -1, 2)$ points the same way and is easier to use. To make the basis orthonormal, divide by the lengths $\sqrt2$ and $\sqrt6$: $\tfrac{1}{\sqrt2}(1, 1, 0)$ and $\tfrac{1}{\sqrt6}(1, -1, 2)$. Both still span the same plane as $\mathbf a_1, \mathbf a_2$, because $\mathbf u_2$ is a combination of $\mathbf a_2$ and $\mathbf a_1$.

Coefficients: $\tfrac{3 + 1}{2} = 2$, then $\tfrac{3 - 1}{2} = 1$, then $\tfrac{2}{1} = 2$. So $\mathbf w = 2(1, 1, 0) + 1(1, -1, 0) + 2(0, 0, 1)$. Check: $(2 + 1,\ 2 - 1,\ 2) = (3, 1, 2)$ ✓. For a basis that is not orthogonal this would be a $3\times3$ system; here it is three independent one-line computations.

So $\mathbf p = \tfrac32(1, 1, 0) + \tfrac23(1, -1, 1) = \left(\tfrac{13}{6}, \tfrac56, \tfrac23\right)$. The error is $\mathbf b - \mathbf p = \left(-\tfrac76, \tfrac76, \tfrac73\right) = \tfrac76(-1, 1, 2)$. Check it is perpendicular to the plane: $(-1, 1, 2)\cdot(1, 1, 0) = 0$ ✓ and $(-1, 1, 2)\cdot(1, -1, 1) = -1 - 1 + 2 = 0$ ✓. The distance from $\mathbf b$ to the plane is $|\mathbf b - \mathbf p| = \tfrac76\sqrt6$.

The two equations are the two orthogonality conditions: the residual vector is perpendicular to the column of $x$-values and to the column of ones. The second one, divided by $n$, says the line passes through the centroid $(\bar x, \bar y)$ of the data. Those two residual sums are also the fastest check on the arithmetic — if either is not zero, something went wrong.

Solve by Cramer's rule: the determinant is $14\cdot4 - 6\cdot6 = 20$, so $m = \tfrac{12\cdot4 - 6\cdot5}{20} = \tfrac{18}{20} = \tfrac{9}{10}$ and $c = \tfrac{14\cdot5 - 6\cdot12}{20} = -\tfrac{2}{20} = -\tfrac{1}{10}$. The line is $y = 0.9x - 0.1$. Residuals $y_i - (0.9x_i - 0.1)$: $0.1,\ 0.2,\ -0.7,\ 0.4$. Checks: they sum to $0$ ✓, and $\sum x_ir_i = 0 + 0.2 - 1.4 + 1.2 = 0$ ✓. The centroid $(1.5, 1.25)$ is on the line: $0.9\cdot1.5 - 0.1 = 1.25$ ✓.

Solve $3x + 2y = 7$, $2x + 6y = 12$: the determinant is $18 - 4 = 14$, so $x = \tfrac{7\cdot6 - 2\cdot12}{14} = \tfrac{18}{14} = \tfrac97$ and $y = \tfrac{3\cdot12 - 2\cdot7}{14} = \tfrac{22}{14} = \tfrac{11}{7}$. The residual is $\mathbf b - A\hat{\mathbf x} = \left(2 - \tfrac{20}{7},\ 0 + \tfrac27,\ 5 - \tfrac{31}{7}\right) = \left(-\tfrac67, \tfrac27, \tfrac47\right)$. Check against both columns: $\tfrac{-6 + 2 + 4}{7} = 0$ ✓ and $\tfrac{-6 - 2 + 8}{7} = 0$ ✓. The smallest possible squared error is $\tfrac{36 + 4 + 16}{49} = \tfrac87$.

This $c\mathbf v$ is also the closest point on the line: for any other multiple $t\mathbf v$, Pythagoras gives $|\mathbf u - t\mathbf v|^2 = |\mathbf u - c\mathbf v|^2 + |c\mathbf v - t\mathbf v|^2 \ge |\mathbf u - c\mathbf v|^2$. $\blacksquare$

Orthogonality to all columns at once is $A^{\mathsf T}(\mathbf b - A\hat{\mathbf x}) = \mathbf 0$, i.e. $A^{\mathsf T}A\hat{\mathbf x} = A^{\mathsf T}\mathbf b$. Fitting a constant to data makes this one equation whose solution is the mean. $\blacksquare$

Why that particular multiple: write the along part as $c\mathbf v$ and demand that the remainder be perpendicular to $\mathbf v$. Then $(\mathbf u - c\mathbf v)\cdot\mathbf v = \mathbf u\cdot\mathbf v - c\,\mathbf v\cdot\mathbf v = 0$, which has exactly one solution, $c = \tfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v}$ — the formula is forced, not chosen. For $\mathbf u = (3, 4)$ and $\mathbf v = (1, 1)$: $c = \tfrac72$, the along part is $(\tfrac72, \tfrac72)$, the across part is $(-\tfrac12, \tfrac12)$, and the Pythagorean bookkeeping checks: $\tfrac{49}{2} + \tfrac12 = 25 = |\mathbf u|^2$.

Step 1 — the coefficient: $c = \dfrac{\mathbf u\cdot\mathbf v}{\mathbf v\cdot\mathbf v} = \dfrac{3 + 4}{1 + 1} = \dfrac72$.

Step 2 — the along part: $\tfrac72(1,1) = \left(\tfrac72, \tfrac72\right)$.

Step 3 — the across part: $(3,4) - \left(\tfrac72,\tfrac72\right) = \left(-\tfrac12, \tfrac12\right)$; check orthogonality: $\left(-\tfrac12\right)(1) + \tfrac12(1) = 0$ ✓.

Step 4 — distance from $(3,4)$ to the line $y = x$: the across length, $\sqrt{\tfrac14 + \tfrac14} = \tfrac{\sqrt2}{2}$ — matching the point-to-line formula $\tfrac{|3-4|}{\sqrt2}$ ✓.

Step 5 — Pythagoras audit: $\left(\tfrac{7\sqrt2}{2}\right)^2 + \left(\tfrac{\sqrt2}{2}\right)^2 = \tfrac{49}{2} + \tfrac12 = 25 = |\mathbf u|^2$ ✓. Five steps, three self-checks — the decomposition verifies itself.

Step 1 — the (unsolvable) system: $c = 1$, $m + c = 2$, $2m + c = 4$, i.e. $A = \begin{pmatrix}0&1\\1&1\\2&1\end{pmatrix}$, $\mathbf b = (1,2,4)$.

Step 2 — normal equations $A^{\mathsf T}A\hat{\mathbf x} = A^{\mathsf T}\mathbf b$: compute $A^{\mathsf T}A = \begin{pmatrix}5&3\\3&3\end{pmatrix}$ and $A^{\mathsf T}\mathbf b = \begin{pmatrix}10\\7\end{pmatrix}$.

Step 3 — solve: $5m + 3c = 10$ and $3m + 3c = 7$; subtracting, $2m = 3$, $m = \tfrac32$, then $c = \tfrac{7 - 4.5}{3} = \tfrac56$.

Step 4 — the fitted line $y = \tfrac32x + \tfrac56$ predicts $\tfrac56, \tfrac{7}{3}, \tfrac{23}{6}$; residuals $\tfrac16, -\tfrac13, \tfrac16$ sum to $0$ — as they must, since orthogonality of the error to the all-ones column is literally one of the normal equations.