Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 62 · Determinants and Orthogonality

Least Squares

Solve overdetermined systems with least squares: normal equations, np.linalg.lstsq, fitting a line and a parabola, reading residuals, and why the error is orthogonal.

Real data almost never fits exactly. You measure ten points and want a line through them; you have a hundred equations and three unknowns. A system with more equations than unknowns is called overdetermined, and usually it has no solution at all: no choice of unknowns satisfies every equation. Least squares answers the practical question instead: which choice of unknowns comes closest?

The answer is a projection. This lesson turns that idea into the normal equations, solves them with NumPy, fits lines and curves, and shows how to read the residuals.

Too many equations

Many points One measurement per equation.
Few knobs Slope and intercept, say.
No exact fit Noise breaks every equation a little.
1 / 2

Why no exact solution

Suppose A is 6 by 2 and you want Ax = b. The columns of A span at most a 2-dimensional plane inside R⁶. A random b almost surely sticks out of that plane, so b is not in the column space and the system is inconsistent.

Instead of demanding Ax = b, we minimize the size of the residual r = b − Ax:

TEXT
minimize  |b − Ax|² = r₁² + r₂² + … + r_m²

Squaring has two nice effects: it makes positive and negative errors count the same, and it makes the problem smooth enough to solve with linear algebra. The vector Ax is the point of the column space nearest to b, which is exactly the projection p. The residual is the perpendicular error.

The normal equations

Perpendicular error means Aᵀ(b − Ax̂) = 0, so

TEXT
AᵀA x̂ = Aᵀb

If the columns of A are independent, AᵀA is a square, symmetric, invertible matrix and the solution is unique. Let's fit a line y = c₀ + c₁t to six noisy points. Each point (tᵢ, yᵢ) gives one equation c₀ + c₁tᵢ = yᵢ, so the matrix has a column of ones and a column of t values. This is called the design matrix.

Python Fitting a line with the normal equations

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line is the geometry in action: the residual vector is orthogonal to both columns of A. That means the residuals sum to zero (orthogonal to the column of ones) and are uncorrelated with t.

np.linalg.lstsq

Forming AᵀA squares the condition number, which can destroy accuracy when the columns are nearly dependent (see the QR lesson). np.linalg.lstsq solves the problem through an SVD-based routine and also copes with rank-deficient matrices. It returns four things: the solution, the sum of squared residuals, the rank of A and its singular values.

Python np.linalg.lstsq and its four return values

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

rcond=None tells NumPy to use the current default cutoff for deciding which singular values count as zero, and silences a deprecation warning in older versions. np.polyfit lists the highest power first, hence the reversal.

Seeing the fit

A picture shows what "closest" means: the line passes between the points, and the vertical gaps are the residuals.

Python Plot the data, the line and the residuals

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Fitting curves

"Linear" in linear least squares means linear in the unknown coefficients, not in t. To fit a parabola y = c₀ + c₁t + c₂t², add a column of t² to the design matrix. Any set of fixed basis functions works the same way: sin t, eᵗ, log t, and so on.

Python Fitting a parabola

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The parabola has a much smaller sum of squared errors because the data really does curve. A bigger model always fits the training data at least as well, so a lower error alone does not prove the bigger model is better. With as many parameters as points you can match the data perfectly and still predict new points badly (overfitting).

Rank-deficient or nearly dependent columns make the solution unstable. If lstsq reports a rank lower than the number of columns, the solution is not unique, and NumPy returns the one with the smallest norm. Standardizing columns and, when needed, adding a small penalty (ridge regression, see the regression project) restores stability.

Reading the residuals

After fitting, always look at the residuals. If the model is appropriate they scatter randomly around zero. A visible pattern (a curve, a trend that grows with t) means the model is missing something. A common summary is the coefficient of determination R² = 1 − SSE/SST, where SST is the total squared deviation of y from its mean.

Python A summary of fit quality

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What does least squares minimize?

    Least squares picks x so that the squared length of the residual vector is as small as possible.
  2. 2. Which equation defines the least squares solution x-hat?

    The residual must be orthogonal to the columns of A, so A^T (b - A x) = 0, which rearranges to the normal equations.
  3. 3. To fit y = c0 + c1 t + c2 t^2 with least squares, what are the columns of the design matrix?

    Each column is a basis function evaluated at all the data points, and the unknowns are the coefficients in front of them.
  4. 4. Why is np.linalg.lstsq usually better than solving A^T A x = A^T b directly?

    Forming A^T A makes ill-conditioning much worse. lstsq works from A itself through an SVD.
  5. 5. The residuals of a least squares fit that includes a column of ones always have which property?

    The residual is orthogonal to every column of A, including the column of ones, so its entries add up to zero.

Summary

  • An overdetermined system usually has no exact solution; least squares finds x̂ minimizing |b − Ax|².
  • Geometrically, Ax̂ is the projection of b onto the column space, and the residual is orthogonal to it.
  • The normal equations AᵀA x̂ = Aᵀb give the answer; in practice call np.linalg.lstsq, or use QR or the SVD, for numerical accuracy.
  • Build the design matrix from basis functions (ones, t, t², …) to fit lines and curves.
  • Always inspect residuals; more parameters reduce training error but can overfit.

Next up: Eigenvalues and Eigenvectors, the special directions of a matrix.