Set of solutions to the least-squares problem via QR decomposition
The set of solutions to the least-squares problem

where , and
are given, can be expressed in terms of the full QR decomposition of
:

where is upper triangular and invertible,
is a permutation matrix, and
is
and orthogonal.
Precisely we have , with
a matrix whose columns span the nullspace of
:

Proof: Since and
are orthogonal, we have, with
:

Exploiting the fact that leaves Euclidean norms invariant, we express the original least-squares problem in the equivalent form:

Once the above is solved, and is found, we recover the original variable
with
.
Now let us decompose and
in a manner consistent with the block structure of
, with
two
-vectors. Then

which leads to the following expression for the objective function:

The optimal choice for the variables is to make the first term zero, which is achievable with

where is free and describes the ambiguity in the solution. The optimal residual is
.
We are essentially done: with , we can write

that is: , with
