The Ordinary Least-Squares (OLS, or LS) problem is defined as
where , are given. Together, the pair is referred to as the problem data. The vector is often referred to as ‘‘measurement‘‘ or “output” vector, and the data matrix as the ‘‘design‘‘ or ‘‘input‘‘ matrix. The vector is referred to as the residual error vector.
Note that the problem is equivalent to one where the norm is not squared. Taking the squares is done for convenience of the solution.
We can interpret the problem in terms of the columns of , as follows. Assume that , where is the -th column of , . The problem reads
In this sense, we are trying to find the best approximation of in terms of a linear combination of the columns of . Thus, the OLS problem amounts to project (find the minimum Euclidean distance) the vector on the span of the vectors 's (that is to say: the range of ).
As seen in the picture, at optimum the residual vector is orthogonal to the range of .
Example: Image compression via least-squares.
The OLS can be interpreted as finding the smallest (in Euclidean norm sense) perturbation of the right-hand side, , such that the linear equation
becomes feasible. In this sense, the OLS formulation implicitly assumes that the data matrix of the problem is known exactly, while only the right-hand side is subject to perturbation, or measurement errors. A more elaborate model, total least-squares, takes into account errors in both and .
In this sense, we are trying to fit of each component of as a linear combination of the corresponding input , with as the coefficients of this linear combination.
Assume that the matrix is tall () and full column rank. Then the solution to the problem is unique, and given by
This can be seen by simply taking the gradient (vector of derivatives) of the objective function, which leads to the optimality condition . Geometrically, the residual vector is orthogonal to the span of the columns of , as seen in the picture above.
We can also prove this via the QR decomposition of the matrix : with a matrix with orthonormal columns () and a upper-triangular, invertible matrix. Noting that
and exploiting the fact that is invertible, we obtain the optimal solution . This is the same as the formula above, since
Thus, to find the solution based on the QR decomposition, we just need to implement two steps:
Rotate the output vector: set .
Solve the triangular system by backwards substitution.
In Matlab, the backslash operator finds the (unique) solution when is full column rank.Matlab syntax
>> x = A\y;
Recall that the optimal set of an minimization problem is its set of minimizers. For least-squares problems, the optimal set is an affine set, which reduces to a singleton when is full column rank.
In the general case ( not necessarily tall, and /or not full rank) then the solution may not be unique. If is a particular solution, then is also a solution, if is such that , that is, . That is, the nullspace of describes the ambiguity of solutions. In mathematical terms:
The formal expression for the set of minimizers to the least-squares problem can be found again via the QR decomposition. This is shown here.