01 / 20

Linear Regression
via Least Squares

Learn how to find the best-fit line through data points by minimizing squared errors: the foundation of predictive modeling.

Linear Algebra

What Is Linear Regression?

Given a set of data points \( (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \), we want to find the straight line \( y = mx + b \) that best fits the data. "Best fit" means the line is as close as possible to all points simultaneously.

Data Points and the Best-Fit Line

x y
\( y = mx + b \)
 residuals

Understanding Residuals

For a line \( y = mx + b \), the residual at data point \( (x_i, y_i) \) is the difference between the actual \( y \)-value and the predicted value:

A positive residual means the point lies above the line; a negative residual means it lies below. The goal of least squares is to make all residuals as small as possible.

✓ Point above line
\( e_i > 0 \): actual value exceeds prediction
✕ Point below line
\( e_i < 0 \): prediction exceeds actual value

Why Squared Errors?

We minimize the sum of squared residuals (SSR), not just the sum of residuals. Why? Because positive and negative residuals would cancel each other out. Squaring ensures every error contributes positively:

1
Prevents cancellation: a point +3 above and one -3 below sum to 0, but \( 9 + 9 = 18 \) in squared error.
2
Penalizes large errors more: an error of 4 counts as 16, not just 4. Outliers are weighted heavily.
3
Smooth and differentiable: the squared function has a nice parabolic shape, guaranteeing a unique minimum.

The Normal Equation

To minimize \( S(m, b) \), we take partial derivatives with respect to \( m \) and \( b \), set them to zero, and solve. In matrix form, the solution is elegantly compact:

Building the Design Matrix

For a line \( y = mx + b \), each data point \( (x_i, y_i) \) gives us the equation \( mx_i + b = y_i \). Stack all equations into a matrix system \( A\hat{\mathbf{x}} = \mathbf{b} \):

\( A = \begin{bmatrix} \color{#818cf8} x_1 & \color{#4ade80} 1 \\ \color{#818cf8} x_2 & \color{#4ade80} 1 \\ \color{#818cf8} x_3 & \color{#4ade80} 1 \\ \color{#94a3b8} \vdots & \color{#94a3b8} \vdots \\ \color{#818cf8} x_n & \color{#4ade80} 1 \end{bmatrix} \) \( \hat{\mathbf{x}} = \begin{bmatrix} \color{#fbbf24} m \\ \color{#fbbf24} b \end{bmatrix} \) \( \mathbf{b} = \begin{bmatrix} \color{#f87171} y_1 \\ \color{#f87171} y_2 \\ \color{#f87171} y_3 \\ \color{#94a3b8} \vdots \\ \color{#f87171} y_n \end{bmatrix} \)

Geometric Interpretation

The system \( A\hat{\mathbf{x}} = \mathbf{b} \) usually has no exact solution because the data points don't lie exactly on a line. The vector \( \mathbf{b} \) is not in the column space of \( A \).

Col(A)
\( \mathbf{b} \)
\( A\hat{\mathbf{x}} \)
\( \mathbf{e} \)

Exact Solution vs. Least Squares

Exact Solution Least Squares
System \( A\mathbf{x} = \mathbf{b} \) \( A^T A \hat{\mathbf{x}} = A^T \mathbf{b} \)
When it works \( \mathbf{b} \in \text{Col}(A) \) Always (if \( A^T A \) invertible)
Number of equations \( n = \) number of unknowns \( n \gg \) number of unknowns
Residual \( \mathbf{e} = \mathbf{0} \) \( \mathbf{e} \) minimized, not zero
Use case Determined systems Overdetermined (data fitting)

How to Apply Least Squares

1
Organize your data into the design matrix \( A \) (with a column of ones for the intercept) and observation vector \( \mathbf{b} \).
2
Compute \( A^T A \) by multiplying the transpose of \( A \) with \( A \). This yields a small square matrix.
3
Compute \( A^T \mathbf{b} \) by multiplying the transpose of \( A \) with the observation vector.
4
Solve \( A^T A \, \hat{\mathbf{x}} = A^T \mathbf{b} \) for \( \hat{\mathbf{x}} \) using elimination or by computing \( (A^T A)^{-1} A^T \mathbf{b} \).
5
Interpret the result: the entries of \( \hat{\mathbf{x}} \) give you the slope \( m \) and intercept \( b \) of the best-fit line.

Example: Three Data Points

Find the best-fit line \( y = mx + b \) for the points \( (1, 1) \), \( (2, 3) \), \( (3, 3) \).

1 2 3 1 2 3 4 (1, 1) (2, 3) (3, 3) best fit

Example: Computing the Solution

Example: Four Data Points

Fit a line to \( (0, 1) \), \( (1, 3) \), \( (2, 4) \), \( (3, 4) \).

Verifying with Residuals

For Example 2 with \( y = x + \frac{3}{2} \), let's check the residuals at each point:

Point Predicted \( \hat{y} \) Residual \( e_i \) \( e_i^2 \)
\( (0, 1) \) \( 1.5 \) \( -0.5 \) \( 0.25 \)
\( (1, 3) \) \( 2.5 \) \( 0.5 \) \( 0.25 \)
\( (2, 4) \) \( 3.5 \) \( 0.5 \) \( 0.25 \)
\( (3, 4) \) \( 4.5 \) \( -0.5 \) \( 0.25 \)

Common Mistakes

✕ Forgetting the column of ones
The design matrix \( A \) needs a column of ones for the intercept \( b \). Without it, you force the line through the origin.
✕ Confusing \( A \) with \( A^T A \)
You cannot invert \( A \) directly when it is not square. You must form \( A^T A \) first, then invert that square matrix.
✕ Minimizing absolute errors
Least squares minimizes squared errors, not absolute values. Using \( |e_i| \) instead of \( e_i^2 \) gives a different (and harder) optimization.

Key Formulas Summary

Concept Formula
Residual \( e_i = y_i - (mx_i + b) \)
Objective \( S = \sum e_i^2 \)
Normal Equation \( A^T A \hat{\mathbf{x}} = A^T \mathbf{b} \)
Closed-Form Solution \( \hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b} \)
Slope (direct formula) \( m = \frac{n\sum x_i y_i - \sum x_i \sum y_i}{n\sum x_i^2 - (\sum x_i)^2} \)
Intercept \( b = \bar{y} - m\bar{x} \)

Question 1 of 5

The least squares method minimizes which quantity?

Question 2 of 5

For fitting a line \( y = mx + b \) to \( n \) data points, the design matrix \( A \) has dimensions:

Question 3 of 5

Given data points \( (1, 2) \) and \( (3, 4) \), what is \( A^T A \)?

Question 4 of 5

In the geometric interpretation, the error vector \( \mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}} \) is:

Question 5 of 5

If you forget the column of ones in the design matrix \( A \), your best-fit line will: