QR Factorization

Definition

An orthogonal transformation to a triangular form (see: Triangular Least Squares Problems) is accomplished using QR Factorization, which for an \(m \times n\) matrix \(\mathbf{A}\) with \(m > n\), has the form

\[ \mathbf{A}= \mathbf{Q} \begin{bmatrix} \mathbf{R} \\ \mathbf{O} \end{bmatrix}, \]

where \(\mathbf{Q}\) is an \(m \times m\) orthogonal matrix and \(\mathbf{R}\) is an \(n \times n\) upper triangular matrix.

Such a factorization transforms the linear least squares problem \(\mathbf{Ax} \cong \mathbf{b}\) into a triangular least squares problem having the same equation:

\[ ||\mathbf{r}||_{2}^{2} = ||\mathbf{b-Ax}||_{2}^{2} = ||\mathbf{b-Q\begin{bmatrix} \mathbf{R} \\ \mathbf{O} \end{bmatrix}} \mathbf{x}||_{2}^{2} = ||\mathbf{Q^{\top}b} - \begin{bmatrix} \mathbf{R} \\ \mathbf{O} \end{bmatrix}\mathbf{x}||_{2}^{2} = ||\mathbf{c}_{1} - \mathbf{Rx}||_{2}^{2} + ||\mathbf{c}_{2}||^{2}_{2}, \]

where the transform right hand side

\[ \mathbf{Q^{\top}b} = \begin{bmatrix} \mathbf{c}_{1} \\ \mathbf{c}_{2} \end{bmatrix} \]

is partitioned such that \(\mathbf{c}_{1}\) is an \(n\)-vector. The solution \(\mathbf{x}\) then satisfies the \(n \times n\) triangular linear system \(\mathbf{Rx = c}_{1}\), and the minimum residual norm is given by \(||\mathbf{r}||_{2}^{2} = ||\mathbf{c}_{2}||_{2}^{2}\).

References

Check Triangular Least Squares Problems if you dont understand the equations.