QR decomposition

1 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\left[\begin{array}{c}\hfill R\hfill \\ \hfill 0\hfill \end{array}\right]$$

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^{T}A)}^{-1}{A}^{T}b$$

becomes

$$x={(R^T{Q}^{T}QR)}^{-1}{R}^T{Q}^{T}b={(R^{T}R)}^{-1}{R}^T{Q}^{T}b=R^{-1}{Q}^{T}b$$

This is a matrix-vector multiplication $Q^{T}b$, followed by the solution of the triangular system $Rx=Q^{T}b$ by back-substitution. The QR factorization saves us the formation of $A^{T}A$ 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.