Why is QR factorization useful and important?

Question

Why do we need QR factorization? Is this used in any particular field?

Answer 1

$\def\R{\mathbb R}\def\norm#1{\left\|#1\right\|}\def\Mat{\mathrm{Mat}}$ QR-factorisation can, for example, be used to solve linear least squares approximation problems as follows: Given $n \le m$, $A \in \Mat_{m,n}(\R)$ with full rank $n$, $b \in \R^m$ \[ \mathrm{find}\ x \in \R^n : \norm{Ax - b}_2 = \min \] Computing the QR-factorisation of $A$, we write $A = QR$ with $Q \in O(m)$, $R \in \Mat_{m,n}(\R)$ upper triangular. Now, as the $2$-norm is invariant under multiplication with orthogonal matrices, \[ \norm{Ax- b}_2 = \norm{Q^{-1}Ax - Q^{-1}b}_2 = \norm{Rx - Q^{-1}b}_2 \] As $m \ge n$, $R$ is of the form $R = \begin{pmatrix} R' \\ 0\end{pmatrix}$ with $R' \in \Mat_n(\R)$ upper triangular. Writing $Q^{-1}b = \begin{pmatrix} y_1 \\ y_2\end{pmatrix}, x = \begin{pmatrix} x_1\\ x_2\end{pmatrix} \in \R^n \times \R^{m-n}$, we have \[ \norm{Ax - b}_2 = \sqrt{\norm{Rx_1 - y_1}^2 + \norm{y_2}^2} \] as $\mathop{\mathrm{rank}} R' = \mathop{\mathrm{rank}} A = n$, $R'$ is invertible and hence we need $x = R'^{-1}y_1$ for minimisation.

---

Another thing, QR factorisation can be useful for is numerical approximation of eigenvectors and -values of a symmetric matrix $A$. Let $A_0 = A$, $A_{k+1} = R_kQ_k$ with $A_k = Q_kR_k$ the QR-decomposition of $A$. One can show that $Q_k \to Q$ and $R_k \to \Lambda$ where $\Lambda$ contains the eigenvalues of $A$ along its diagonal and $Q$ the eigenvectors in its columns.

Answer 2

One hidden but very useful property of the QR decomposition - the order of rows of the $Q$ matrix is important. Not just do the rows form an orthonormal basis (which would be useful on its own), but the first row of $Q$ is along the same direction as the first row of the original matrix. The first two rows of $Q$ span the same 2-d space as the first two rows of the original matrix and so on. And since $Q$ is orthonormal, it is either a rotation matrix or can easily be converted into a rotation matrix by multiplying one of the rows by $-1$. These facts together are very useful when you want to do rotations in higher dimensional space, preserving certain planes (making sure they are not impacted by the rotation).

Answer 3

QR Factorization records the orthogonalization of a matrix, namely, the construction of an orthogonal set that spans the space of column vectors of A. Doing calculations with orthogonal matrices is preferable because (1) they are easy to invert by definition, and (2) they do not magnify errors.