Linear least squares

Linear least squares

Linear least squares is a mathematical optimization technique to find an approximate solution for a system of linear equations that has no exact solution. This usually happens if the number of equations is bigger than the number of variables.

Table of contents

1 Definition
2 Computation
3 Applications
4 See also

Definition

In mathematical terms we want to find a solution for the "equation"

Ax ≈ b,

where A is an m-by-n matrix (m > n) and x and b are n- resp. m-dimensional column vectors. More precisely, we want to minimize the euclidean norm of the residual (b − Ax). (Hence "least squares").

It turns out, that an x that minimizes the above equation also solves the normal equation

A^TAx = A^Tb,

where A^T means A transposed. Note that this just corresponds to a usual system of linear equations. The solution is unambigious if the rank of A is n.

Computation

The normal equation can be solved like any other equation system, yet an efficient and numerically stable method can be obtained by first computing the QR decomposition of the matrix A.

Then, with A = QR, where Q is an orthogonal matrix and R is an upper triangular matrix, the normal equation simplifies to

Rx = Q^Tb.

Applications

The linear least squares method can be used to find a linear function Rⁿ → R that best fits a given set of data (see general least squares method).

We write the linear function we try to find as a 1-by-n matrix x^T (so x is actually a column vector, see also linear transformation).

The set of data consists of m (n+1)-tuples (x₁, ..., x_n, y). Those can be written into an m-by-n matrix A and a vector b, where every tuple corresponds to a row of A, the y becoming the corresponding entry in b.

Then,

Ax ≈ b

yields the function x we seek.