Ordinary Least-Squares Problem

Least-Squares > Ordinary LS | Variants | Kernels | Applications

Definition
Interpretations
Solution via QR decomposition (full rank case)
Optimal solution (general case)

Definition

where $A in mathbf{R}^{m times n}$ , $y in mathbf{R}^m$ are given. Together, the pair (A,y)

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 r := y-Ax

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.

Interpretations

Interpretation as projection on the range

Interpretation as minimum distance to feasibility

The OLS problem is usually applied to problems where the linear Ax = y

is not feasible, that is, there is no solution to Ax = y

The OLS can be interpreted as finding the smallest (in Euclidean norm sense) perturbation of the right-hand side, delta y

, 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

Interpretation as regression

We can also interpret the problem in terms of the rows of

, as follows. Assume that A^T = [a_1, ldots, a_m]

, where $a_i^T in mathbf{R}^m$ is the

-th row of

. The problem reads

In this sense, we are trying to fit of each component of

as a linear combination of the corresponding input a_i

, with

as the coefficients of this linear combination.

Solution via QR decomposition (full rank case)

Assume that the matrix A in mathbf{m times n}

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 A^T(Ax-y) = 0

. Geometrically, the residual vector Ax-y

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

matrix with orthonormal columns ( Q^TQ = I_n

) and

upper-triangular, invertible matrix. Noting that

and exploiting the fact that

is invertible, we obtain the optimal solution $x^ast = R^{-1}Q^Ty$ . This is the same as the formula above, since

$(A^TA)^{-1} A^Ty = (R^TQ^TQR)^{-1}R^TQ^Ty = (R^TR)^{-1} R^TQ^Ty = R^{-1} Q^Ty.$

Thus, to find the solution based on the QR decomposition, we just need to implement two steps:

In Matlab, the backslash operator finds the (unique) solution when

is full column rank.

Matlab syntax

>> x = A\y;

Optimal solution and optimal set

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 x^0

is a particular solution, then x=x^0+z

is also a solution, if

is such that Az=0

, that is, z in mathbf{N}(A)

. 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.