QR Decomposition

87. QR Decomposition

Every $𝑚 \times 𝑛$ matrix $𝐴$ with $𝑚 \geq 𝑛$ can be factored as:

𝐴 = 𝑄 𝑅

where:

If $𝐴$ is full column rank, the decomposition is unique up to signs on the diagonal of $𝑅$ .

For square $𝐴$ (full rank), $𝑄$ is a full orthogonal matrix and $𝑅$ is square upper triangular.

The columns of $𝑄$ are the result of applying Gram–Schmidt orthogonalization to the columns of $𝐴$ :

Explicitly, $𝑅_{𝑖 𝑗} = 𝑞_{𝑖}^{𝑇} 𝑎_{𝑗}$ for $𝑖 \leq 𝑗$ and $0$ for $𝑖 > 𝑗$ .

Example

𝐴 = [\begin{matrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{matrix}]

Apply Gram–Schmidt to columns:

$𝑞_{1} = \frac{𝑎_{1}}{‖} 𝑎_{1} ‖ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}]$
Project $𝑎_{2}$ off $𝑞_{1}$ : $𝑎_{2} - (𝑞_{1}^{𝑇} 𝑎_{2}) 𝑞_{1} = [\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}] - \frac{1}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}] = [\begin{matrix} - \frac{1}{2} \\ \frac{1}{2} \\ 1 \end{matrix}]$
$𝑞_{2} =$ that, normalized: $\frac{1}{\sqrt{6}} [\begin{matrix} - 1 \\ 1 \\ 2 \end{matrix}]$

𝑄 = [\begin{matrix} \frac{1}{\sqrt{2}} & - \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\ 0 & \frac{2}{\sqrt{6}} \end{matrix}]

𝑅 = 𝑄^{𝑇} 𝐴 = [\begin{matrix} \sqrt{2} & \frac{1}{\sqrt{2}} \\ 0 & \sqrt{\frac{3}{2}} \end{matrix}]

QR is the workhorse for least-squares problems:

Given $𝐴 \vec{𝑥} = \vec{𝑏}$ overdetermined (more equations than unknowns), the least-squares solution

\hat{\vec{𝑥}} = arg min_{\vec{𝑥}} ‖ 𝐴 \vec{𝑥} - \vec{𝑏} ‖^{2}

solves the normal equations $𝐴^{𝑇} 𝐴 \vec{𝑥} = 𝐴^{𝑇} \vec{𝑏}$ . Using $𝐴 = 𝑄 𝑅$ :

𝑅 \vec{𝑥} = 𝑄^{𝑇} \vec{𝑏}

Then back-substitute on the upper-triangular $𝑅$ — much more numerically stable than forming $𝐴^{𝑇} 𝐴$ directly.

Other uses:

Eigenvalue computation via the QR algorithm — iteratively factor $𝐴_{𝑘} = 𝑄_{𝑘} 𝑅_{𝑘}$ and update $𝐴_{𝑘 + 1} = 𝑅_{𝑘} 𝑄_{𝑘}$ ; converges to a triangular matrix whose diagonal gives the eigenvalues
Orthonormalizing a basis numerically (Gram–Schmidt is unstable in floating point; Householder QR is much more reliable)
Solving square systems as an alternative to LU

Classical Gram–Schmidt — conceptually clean but numerically unstable
Modified Gram–Schmidt — small variation, much more stable
Householder reflections — uses orthogonal reflections, very stable, $𝑂 (𝑚 𝑛^{2})$
Givens rotations — useful for sparse / structured matrices