Least Squares

Summary

Linear least squares chooses parameters of a model that is linear in those parameters by minimizing the sum of squared residuals. For a straight line, the normal equations give a unique solution when the $x_{i}$ are not all equal.

Prerequisites

Summation notation and $2 \times 2$ linear systems
Curve Fitting
Optional: matrix form $A^{⊤} A \hat{a} = A^{⊤} y$

Problem Type

Given data $(x_{i}, y_{i})_{i = 1}^{n}$ , fit $f (x) = a + b x$ (or a polynomial linear in coefficients) by minimizing

E (a, b) = \sum_{i = 1}^{n} (y_{i} - (a + b x_{i}))^{2} .

Method Definition

Set $\partial E / \partial a = 0$ and $\partial E / \partial b = 0$ to obtain the normal equations:^[1]

{\begin{cases} n a + b \sum x_{i} = \sum y_{i} \\ a \sum x_{i} + b \sum x_{i}^{2} = \sum x_{i} y_{i} \end{cases}

Matrix form: with design matrix

A = (\begin{matrix} 1 & x_{1} \\ ⋮ & ⋮ \\ 1 & x_{n} \end{matrix}), \hat{a} = (\begin{matrix} a \\ b \end{matrix}), y = (\begin{matrix} y_{1} \\ ⋮ \\ y_{n} \end{matrix}),

A^{⊤} A \hat{a} = A^{⊤} y .

Prefer solving $min ∥ A \hat{a} - y ∥_{2}$ via QR rather than forming $A^{⊤} A$ when $n$ is large or columns are poorly scaled.

Assumptions / Requirements

Model linear in parameters
$A$ full column rank (for a unique minimizer)
Squared error criterion (sensitive to outliers)

Algorithm

Compute sums $n$ , $\sum x$ , $\sum y$ , $\sum x^{2}$ , $\sum x y$ .
Solve the $2 \times 2$ normal system for $(a, b)$ .
Report residuals $r_{i} = y_{i} - (a + b x_{i})$ and $E = \sum r_{i}^{2}$ .

Worked Example 1 — three points

Data: $(1, 2)$ , $(2, 3)$ , $(3, 5)$ .

n = 3, \sum x = 6, \sum y = 10, \sum x^{2} = 14, \sum x y = 23.

{\begin{cases} 3 a + 6 b = 10 \\ 6 a + 14 b = 23 \end{cases}

Multiply the first equation by 2: $6 a + 12 b = 20$ . Subtract from the second: $2 b = 3 \Rightarrow b = 3 / 2$ . Then $3 a + 6 \cdot (3 / 2) = 10 \Rightarrow 3 a + 9 = 10 \Rightarrow a = 1 / 3$ .

Fitted line:

f (x) = \frac{1}{3} + \frac{3}{2} x .

(Intercept $1 / 3$ , slope $1.5$ — not intercept $0.5$ .)

Worked Example 2 — four points

Data: $(1, 2)$ , $(2, 3)$ , $(3, 5)$ , $(4, 4)$ .

n = 4, \sum x = 10, \sum y = 14, \sum x^{2} = 30, \sum x y = 39.

{\begin{cases} 4 a + 10 b = 14 \\ 10 a + 30 b = 39 \end{cases}

From the first equation, $2 a + 5 b = 7$ , so $a = (7 - 5 b) / 2$ . Substitute into the second:

10 \cdot \frac{7 - 5 b}{2} + 30 b = 39 \Rightarrow 5 (7 - 5 b) + 30 b = 39 \Rightarrow 35 + 5 b = 39 \Rightarrow b = 0.8 .

Then $4 a + 8 = 14 \Rightarrow a = 1.5$ . Fitted line: $f (x) = 1.5 + 0.8 x$ .

Error / Accuracy

Minimizing $E$ does not imply every residual is small. Always inspect residuals and, for inference, model assumptions.

Common Failure Modes

Swapping slope and intercept in the normal system
Using $\sum x y = 20$ for the three-point example (correct value is $23$ )
Solving overdetermined systems as if they were square interpolants

Connections

Curve Fitting
Numerical Methods/Linear Systems/Solving Linear Systems
Polynomial Interpolation (exact fit when $m = n + 1$ and degree $n$ )

References

Burden & Faires, Numerical Analysis, least squares; Golub & Van Loan, Matrix Computations; NIST/SEMATECH e-Handbook, https://www.itl.nist.gov/div898/handbook/ ↩︎