QR Decomposition

Orthogonal matrix triangularization (QR decomposition) reduces a real $m \times n$ matrix $A$ with $m \ge n$ and full rank to a much simpler form. It guarantees numerical stability by minimizing errors caused by machine roundoffs. A suitably chosen orthogonal matrix $Q$ will triangularize the given matrix:

$$ A = Q \begin{bmatrix} R \\ 0 \end{bmatrix} $$

with the $n \times n$ right triangular matrix $R$ . One only has then to solve the triangular system $Rx = Pb$ , where $P$ consists of the first $n$ rows of $Q$ .

The least squares problem $Ax \approx b$ is easy to solve with $A = QR$ and $Q$ an orthogonal matrix (here and henceforth $R$ is the entire $ m \times n $ augmented matrix from above). The solution

$$ x = (A^TA)^{-1} A^Tb $$

becomes

$$ x = (R^TQ^TQR)^{-1}R^TQ^Tb = (R^TR)^{-1}R^TQ^Tb = R^{-1}Q^Tb $$

This is a matrix-vector multiplication $Q^Tb$ , followed by the solution of the triangular system $Rx = Q^Tb$ by back-substitution. The QR factorization saves us the formation of $A^TA$ and the solution of the normal equations.

Many different methods exist for the QR decomposition, e.g. the Householder transformation, the Givens rotation, or the Gram-Schmidt decomposition.

Bibliography

1

The Data Analysis Briefbook. http://rkb.home.cern.ch/rkb/titleA.html