Math Detours · Grade 12 · Around the corner · 8

Least squares is a projection

The best-fit line is the shadow of the data on a plane. Derive the normal equations from "the error is perpendicular to the fit".

Name ____________________Date ____________

Tonight's idea

Three data points \((x_i, y_i)\), and you want the line \(y = a + bx\) that fits them best. Least squares defines best: make the residuals \(r_i = y_i - (a + bx_i)\), the vertical misses, have the smallest possible sum of squares.

Now stack the \(y\)-values into one vector \(\mathbf y = (y_1, y_2, y_3)\). The fitted values are a vector too: \(\hat{\mathbf y} = a\mathbf 1 + b\mathbf x\), with \(\mathbf 1 = (1, 1, 1)\) and \(\mathbf x = (x_1, x_2, x_3)\). As \(a, b\) vary, \(\hat{\mathbf y}\) sweeps out a plane through the origin, and \(\sum r_i^2 = |\mathbf y - \hat{\mathbf y}|^2\) is the squared distance from \(\mathbf y\) to it.

1x O y ŷ r every possible fit a1 + bx lies in this plane
The best fit \(\hat{\mathbf y}\) is the shadow of \(\mathbf y\) on the plane; the residual \(\mathbf r\) is perpendicular to it.

The closest point of a plane is the foot of the perpendicular: for any other point \(\mathbf p\) of the plane, Pythagoras gives \(|\mathbf y - \mathbf p|^2 = |\mathbf y - \hat{\mathbf y}|^2 + |\hat{\mathbf y} - \mathbf p|^2\). So the residual \(\mathbf r = \mathbf y - \hat{\mathbf y}\) is perpendicular to \(\mathbf 1\) and to \(\mathbf x\) (dot products zero): \(\mathbf 1 \cdot \mathbf r = 0\), \(\mathbf x \cdot \mathbf r = 0\). Written out, these are the normal equations (normal means perpendicular):

\(\sum y_i = na + b\sum x_i, \qquad \sum x_i y_i = a\sum x_i + b\sum x_i^2.\)

Watch one: \((1, 1), (2, 2), (3, 2)\)

\(n = 3\), \(\sum x = 6\), \(\sum y = 5\), \(\sum xy = 11\), \(\sum x^2 = 14\). The normal equations:

\[5 = 3a + 6b, \qquad 11 = 6a + 14b.\]

Double the first and subtract: \(2b = 1\), so \(b = \tfrac12\) and \(a = \tfrac23\). The line is \(y = \tfrac23 + \tfrac12 x\), with residuals \(\mathbf r = (-\tfrac16, \tfrac13, -\tfrac16)\). Check: \(\mathbf 1 \cdot \mathbf r = 0\) and \(\mathbf x \cdot \mathbf r = -\tfrac16 + \tfrac23 - \tfrac12 = 0\). Sum of squares \(\tfrac{1}{36} + \tfrac19 + \tfrac1{36} = \tfrac16\). Any other line does worse: the one through the end points has sum of squares \(\tfrac14\).

Place points, drag them, and watch the line and residuals move: mathdetours.com/demos/regression.html.

Your turn

  1. Points \((0, 0), (1, 1), (2, 3)\). Write the two normal equations, solve them, and check that \(\sum r_i = 0\) and \(\sum x_i r_i = 0\).
  2. (a) Divide the first normal equation by \(n\). Which point must the line pass through? (b) Fit a constant \(y = a\) by least squares (the only direction is \(\mathbf 1\)). Show \(a = \bar y\).
  3. Points \((1, 2), (2, 3), (3, 5), (4, 6)\). Find the line, the four residuals and the sum of squares. What does the line predict at \(x = 6\)?
  4. A line through the origin, \(y = bx\), has one direction only, \(\mathbf x\). Use \(\mathbf x \cdot \mathbf r = 0\) to find \(b\), and compare with grade 10's projection formula \(\dfrac{\mathbf x \cdot \mathbf y}{\mathbf x \cdot \mathbf x}\,\mathbf x\). Apply it to the example's points and compare the sum of squares with \(\tfrac16\). Why can it not be smaller?

Stretch: a parabola is still "linear"

\(y = a + bx + cx^2\) is still linear in the unknowns \(a, b, c\), so least squares is still a projection, onto the flat spanned by \(\mathbf 1\), \(\mathbf x\) and \(\mathbf x^2 = (x_1^2, \dots, x_n^2)\). Write the three normal equations. For the example's three points, what are the residuals, and why?

Answers

  1. \(\sum x = 3\), \(\sum y = 4\), \(\sum xy = 7\), \(\sum x^2 = 5\). \(4 = 3a + 3b\) and \(7 = 3a + 5b\), so \(b = \tfrac32\), \(a = -\tfrac16\): \(y = -\tfrac16 + \tfrac32 x\). Fitted \(-\tfrac16, \tfrac43, \tfrac{17}{6}\); residuals \(\tfrac16, -\tfrac13, \tfrac16\). \(\sum r_i = 0\) and \(\sum x_i r_i = 0 - \tfrac13 + \tfrac13 = 0\). Sum of squares \(\tfrac16\).
  2. (a) \(\bar y = a + b\bar x\), which says \((\bar x, \bar y)\) is on the line. (b) Only \(\mathbf 1 \cdot \mathbf r = 0\) survives: \(\sum (y_i - a) = 0\), so \(a = \bar y\). The mean is the projection of \(\mathbf y\) onto the line through \(\mathbf 1\).
  3. \(\sum x = 10\), \(\sum y = 16\), \(\sum xy = 47\), \(\sum x^2 = 30\). \(16 = 4a + 10b\), \(47 = 10a + 30b\), so \(b = 1.4\), \(a = 0.5\). Fitted 1.9, 3.3, 4.7, 6.1; residuals \(0.1, -0.3, 0.3, -0.1\); sum of squares 0.2. At \(x = 6\) the line gives 8.9, a prediction outside the range of the data, so trust it less.
  4. \(\mathbf x \cdot (\mathbf y - b\mathbf x) = 0\) gives \(b = \dfrac{\sum x_i y_i}{\sum x_i^2} = \dfrac{\mathbf x \cdot \mathbf y}{\mathbf x \cdot \mathbf x}\), exactly the projection coefficient. For the example, \(b = \tfrac{11}{14}\), residuals \(\tfrac{3}{14}, \tfrac{6}{14}, -\tfrac{5}{14}\), sum of squares \(\tfrac{70}{196} = \tfrac{5}{14} \approx 0.357\), larger than \(\tfrac16\). The line through the origin is one of the candidates in the two-direction plane (the case \(a = 0\)), so the best over the whole plane cannot do worse.

Stretch. \(\mathbf r\) is perpendicular to \(\mathbf 1\), \(\mathbf x\) and \(\mathbf x^2\): \(\sum y_i = na + b\sum x_i + c\sum x_i^2\), \(\sum x_i y_i = a\sum x_i + b\sum x_i^2 + c\sum x_i^3\), \(\sum x_i^2 y_i = a\sum x_i^2 + b\sum x_i^3 + c\sum x_i^4\). With three points and three unknowns, the vectors \(\mathbf 1, \mathbf x, \mathbf x^2\) span all of three-dimensional space (the \(x_i\) are distinct), so \(\mathbf y\) already lies in the flat: every residual is zero. The parabola \(y = -1 + \tfrac52 x - \tfrac12 x^2\) passes through all three points. A perfect fit with as many parameters as points has learned nothing.

← PreviousNext: Gradient descent →