Skip to content

QR Decomposition

Formula

\[ A = Q R \]

Parameters

  • \(A\in\mathbb{R}^{m\times n}\)
  • \(Q\in\mathbb{R}^{m\times n}\): orthonormal columns
  • \(R\in\mathbb{R}^{n\times n}\): upper triangular

What it means

Factorizes a matrix into an orthonormal basis and a triangular matrix.

What it's used for

  • Stable least squares and orthonormalization.
  • Solving \(Ax=b\) without forming \(A^TA\).

Key properties

  • Used for least squares and numerical stability
  • Can be computed via Gram-Schmidt or Householder reflections

Common gotchas

  • "Thin" vs "full" QR shapes differ; be explicit.
  • Classical Gram-Schmidt is numerically unstable.

Example

For \(A=I\), one QR factorization is \(Q=I, R=I\).

How to Compute (Pseudocode)

Input: matrix A (m x n)
Output: Q, R such that A = Q R

compute QR factorization (for example, Householder reflections)
return Q and R (thin or full form, as needed)

Complexity

  • Time: \(O(m n^2)\) for dense QR when \(m \ge n\)
  • Space: \(O(mn)\) for dense matrix/factor storage (implementation-dependent)
  • Assumptions: Dense QR workflow shown; thin vs full QR affects constants and output storage shapes

See also