Suppose we would like to solve the linear system of equations,

where

When the 2-norm is used here, this is referred to as the

An algebraic expression for the solution can be derived from the normal equations,

These equations can be solved using the Cholesky decomposition of :

- Compute .
- Obtain Cholesky decomposition of
*S*, , where*G*is lower triangular. - Let , solve the lower triangular system via forward substitution.
- Solve the upper triangular system, via backward substitution.

A more numerically stable approach is provided by the QR decomposition. Let

where

**Properties of the QRD**. Let

- The columns of form an orthonormal basis for and the columns of form
an orthonormal basis for
. More generally, let

denote submatrices of*A,Q*, respectively. Then

- , where contains the first
*p*rows of*R*. Note that the remaining rows of*R*are 0 and that is upper triangular. This is referred to as the reduced QRD. -

Hence, is the Cholesky factor of the symmetric matrix . - is the projection matrix onto .
- is the projection matrix onto .

To show how these properties generate solutions to least squares problems, let be the full
QRD of *A*. Use the column partition of *Q* defined above to obtain

is an orthogonal matrix and so

Since

Note that just the reduced QRD is needed to obtain the LS solution.

Fitted values are given by

so fitted values are the projection of

which is the projection of

2017-12-10