Use of the QR factorization

Prince, E.; Boggs, P. T.

doi:10.1107/97809553602060000609

International
Tables for
Crystallography
Volume C
Mathematical, physical and chemical tables
Edited by E. Prince

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. C. ch. 8.1, pp. 681-682

Section 8.1.3.1. Use of the QR factorization

E. Prince^a and P. T. Boggs^b

^a NIST Center for Neutron Research, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA, and ^bScientific Computing Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA

8.1.3.1. Use of the QR factorization

| top | pdf |

The linear least-squares problem can be viewed geometrically as the problem of finding the point in a p-dimensional subspace, defined as the set of points that can be reached by a linear combination of the columns of A, closest to a given point, y, in an n-dimensional observation space. Since this is equivalent to finding the orthogonal projection of point y into that subspace, it is not surprising that an orthogonal decomposition of A helps to solve the problem. For convenience in this discussion, let us remove the weight matrix from the problem by defining the standardized design matrix by $[{\bi Z}={\bi UA}, \eqno (8.1.3.1)]$ where U is the upper triangular Cholesky factor of W.

Consider the least-squares problem with the QR factorization of Z, as given in Subsection 8.1.1.1. For y′ = U(y − b), (8.1.2.5) becomes $[\eqalignno{S &=({\bf y}^{\prime }-{\bi Z}{\bf x})^T({\bf y}^{\prime }-{\bi Z}{\bf x}) \cr &=[{\bi Q}^T({\bf y}^{\prime }-{\bi Z}{\bf x})]^T[{\bi Q}^T({\bf y}^{\prime }-{\bi Z}{\bf x})], & (8.1.3.2)}]$ which reduces to $[S=({\bi Q}_{{\bi Z}}^T{\bf y}^{\prime }-{\bi R}{\bf x})^T({\bi Q}_{{\bi Z}}^T{\bf y}^{\prime }-{\bi R}{\bf x})+{\bf y}^{\prime T}{\bi Q}_{\bot }{\bi Q}_{\bot }^T{\bf y}^{\prime }. \eqno (8.1.3.3)]$ The second term in (8.1.3.3) is independent of x, and is therefore the sum of squared residuals. The first term vanishes if $[{\bi R}{\bf x}={\bi Q}_{{\bi Z}}^T{\bf y}^{\prime }, \eqno (8.1.3.4)]$ which, because R is upper triangular, is easily solved for x. The QR decomposition of Z therefore leads naturally to the following algorithm for solving the linear least-squares problem:

(1) compute the QR factorization of Z;
(2) compute $[{\bi Q}_{{\bi Z}}^{T}{\bf y}^{\prime };]$
(3) solve Rx = $[{\bi Q}_{{\bi Z}}^{T}{\bf y}^{\prime }]$ for x.
(4) compute the residual sum of squares by $[{\bf y}^{\prime T}{\bf y}^{\prime }-{\bf y}^{\prime }{\bi Q}_{{\bi Z}}{\bi Q}_{{\bi Z}}^{T}{\bf y}^{\prime }]$ .
(5) compute the variance–covariance matrix from $[{\bi V}_{\bf x} ={\bi R}^{-1}({\bi R}^{-1})^{T}]$ .

References

International Tables for Crystallography (2006). Vol. C. ch. 8.1, pp. 681-682