Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 38 · Linear Algebra

Least Squares and Pseudo-inverses

Solve overdetermined systems with scipy.linalg.lstsq and pinv, fit lines and parabolas, avoid the normal equations trap and use Toeplitz and circulant matrices.

Real data rarely fits a model exactly. You measure 25 points and want a straight line, which has two unknowns. That gives 25 equations and 2 unknowns: an overdetermined system. There is no line that passes through every point, so solve cannot help. What you want instead is the line that comes closest, and "closest" usually means the smallest sum of squared errors. That is least squares.

This lesson shows how to pose a fitting problem as a matrix problem, solve it with scipy.linalg.lstsq, understand the pseudo-inverse behind it, and avoid the classic mistake of using the normal equations. At the end you will meet two special matrix families, Toeplitz and circulant, that appear everywhere in signal processing. If you need a refresher on solve and condition numbers, read Matrices, Solving Systems and Inverses first.

Least squares as a matrix problem

Given a matrix A with more rows than columns and a vector b, least squares looks for the vector x that minimizes the length of the residual b - A @ x:

TEXT
minimize  || A x - b ||²

For a straight line y = m*x + c, each data point gives one row of A: the x-value and a 1 (for the intercept). The unknowns are m and c.

flowchart LR
    D["data points<br/>(x_i, y_i)"] --> A["design matrix A<br/>rows: [x_i, 1]"]
    A --> L["lstsq(A, y)"]
    L --> C["coefficients<br/>[slope, intercept]"]
    L --> R["residual norm,<br/>rank, singular values"]

Fitting a model that is linear in its parameters: build the design matrix, then let lstsq do the rest.

The function scipy.linalg.lstsq returns four things: the solution, the sum of squared residuals (only when the system is overdetermined and has full rank), the numerical rank of A, and the singular values of A.

Python Fit a line with lstsq

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 data was generated from a slope of 2.5 and an intercept of 1.0, and the fit recovers values close to those, thanks to the noise being small. The last line shows the defining property of a least-squares solution: the residual is orthogonal to every column of A, so A.T @ r is zero up to rounding. Geometrically, A @ x is the projection of b onto the column space of A, and the leftover error points straight away from that space.

numpy.linalg.lstsq does the same job. The SciPy version adds a choice of LAPACK driver ('gelsd' by default, 'gelsy', 'gelss') and options such as check_finite=False. For everyday fitting, either works.

Any model that is linear in its parameters

"Linear" refers to the parameters, not to x. A parabola y = a*x² + b*x + c is still a linear least-squares problem, because a, b and c enter linearly. You only change the columns of the design matrix.

Python Fit 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 same recipe handles sines and cosines (np.sin(w*x) as a column), logarithms, or any other fixed functions. When the parameters enter non-linearly, for example exp(-k*x) with unknown k, you need an iterative solver; that is the subject of Curve Fitting and Least Squares.

The pseudo-inverse

For a square invertible matrix, x = inv(A) @ b solves A x = b. For a tall or rank-deficient matrix there is no inverse, but there is a generalization: the Moore-Penrose pseudo-inverse A⁺, computed by scipy.linalg.pinv. Then x = pinv(A) @ b is the least-squares solution, and when many solutions tie, it is the one with the smallest norm.

pinv is built from the singular value decomposition (see Eigenvalues and Singular Values): invert the singular values that are clearly nonzero and ignore the tiny ones.

Python Pseudo-inverse properties

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.

Notice the shapes: pinv of a 3-by-2 matrix is 2-by-3. Ap @ A is the 2-by-2 identity, which is true here because A has full column rank (a left inverse). A @ Ap would not be the 3-by-3 identity; it is a projection matrix onto the column space.

The second half of the example shows why the pseudo-inverse matters. When the columns are dependent, infinitely many x give zero error: any [1 - 2t, t]. lstsq and pinv both pick the shortest one, which is a sensible and unique answer.

Both lstsq and pinv decide what counts as "zero" with a cutoff on singular values (cond= in lstsq, rtol= in pinv). If your result looks wild, print the singular values and check whether the cutoff sits in the right place.

The normal equations trap

A textbook shortcut turns the problem into a square system: multiply both sides by A.T to get (A.T @ A) x = A.T @ b. These are the normal equations, and solve can handle them. It is tempting, and sometimes fine, but it squares the condition number: cond(A.T @ A) = cond(A)². If A is slightly ill-conditioned, A.T @ A can lose all precision, or even become exactly singular.

The classic demonstration is a matrix with one tiny block. Here eps is so small that eps² vanishes when added to 1:

Python Normal equations versus lstsq

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.

A has full rank 3 and lstsq recovers the exact answer. The product A.T @ A, however, turns into a matrix of ones that has rank 1, so the normal equations break down. lstsq works directly on A through orthogonal factorizations, which never square the condition number. The rule: use lstsq (or a QR/SVD solve), not solve(A.T @ A, ...).

Choosing between lstsq, pinv and QR

Tool Use it when
lstsq(A, b) You just need the best-fit x. Default choice.
pinv(A) You need the matrix A⁺ itself, for example to apply it to many right-hand sides, or to study its properties.
qr + solve_triangular Full-rank problems where you want control of the factorization. See LU, QR, Cholesky and Schur Decompositions.
solve(A.T @ A, A.T @ b) Almost never. Only for very well-conditioned, small problems.

For one right-hand side, lstsq(A, b) is cheaper than forming pinv(A) @ b, because it does not build the full pseudo-inverse.

Special matrices: Toeplitz and circulant

Some matrices have so much structure that SciPy can build and solve them quickly. A Toeplitz matrix is constant along each diagonal. It describes convolution and many time-series problems. A circulant matrix is a Toeplitz matrix where each row is the previous one shifted cyclically, which models periodic (wrap-around) convolution.

Python Toeplitz and circulant matrices

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.

Three useful facts show up in the output:

  • toeplitz(first_column, first_row) builds the matrix; with one argument it makes a symmetric one. The second matrix, with 2 on the diagonal and -1 beside it, is the classic second-difference matrix that appears when discretizing a derivative.
  • A circulant system can be solved with the FFT: dividing the transforms of b and of the first column gives the solution in O(n log n) instead of O(n³). The two answers agree.
  • solve_toeplitz uses the Levinson algorithm, which solves a symmetric Toeplitz system in O(n²) time and uses only the first column, so you never store the full matrix. For a few hundred unknowns the gain is small, but for tens of thousands it decides whether a problem is feasible.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does scipy.linalg.lstsq(A, b) minimize?

    Least squares minimizes the squared 2-norm of the residual vector, i.e. the sum of the squared differences between A @ x and b.
  2. 2. Why is solve(A.T @ A, A.T @ b) a risky way to fit data?

    cond(A.T @ A) equals cond(A) squared. An ill-conditioned problem can become numerically singular, while lstsq works on A directly and avoids that.
  3. 3. A matrix has linearly dependent columns, so many solutions fit exactly. Which solution do lstsq and pinv return?

    The pseudo-inverse gives the minimum-norm least-squares solution, which is unique even when the exact solutions form an infinite family.
  4. 4. Which model is still a LINEAR least-squares problem?

    The parameters a, b and c enter linearly, so each term becomes a column of the design matrix. The other models have parameters inside functions or denominators and need iterative fitting.

Summary

  • An overdetermined system (more equations than unknowns) has no exact solution; least squares finds the x that minimizes ||A x - b||².
  • Build a design matrix with one column per basis function, then call scipy.linalg.lstsq(A, b) to get the coefficients, residual sum, rank and singular values.
  • A least-squares residual is orthogonal to the columns of A.
  • pinv gives the Moore-Penrose pseudo-inverse. For rank-deficient problems, lstsq and pinv return the minimum-norm solution.
  • Avoid the normal equations: they square the condition number and can fail outright.
  • toeplitz, circulant and solve_toeplitz exploit structure for fast construction and solving.

Next up: Scalar Minimization and Root Finding, where we leave linear algebra and start searching for minima and zeros of general functions.