QR Decomposition is a matrix factorization technique that breaks a matrix A into a product A = QR, where Q is an orthogonal matrix (its columns are perpendicular unit vectors) and R is an upper triangular matrix (all entries below the main diagonal are zero).
Description
| Simple description |
QR decomposition breaks a matrix into two simpler matrices. Think of it as splitting a complicated shape into a rotation or reflection (Q) and a scaling or shearing (R). This makes complex math problems involving that matrix much easier and faster to solve, especially when dealing with noisy data or finding patterns. |
| Medium-complexity description |
QR decomposition factors a matrix A into the product A = QR, where Q is an orthogonal matrix (its transpose is its inverse) and R is an upper triangular matrix. It is a key algorithm in numerical linear algebra, commonly computed via Gram-Schmidt, Householder reflections, or Givens rotations to ensure numerical stability for solving linear least-squares problems or computing eigenvalues. |
| Technical description |
Given an m×n real or complex matrix A with linearly independent columns, QR decomposition produces A = QR, where Q is an m×m unitary matrix (Q*Q = QQ* = I) and R is an m×n upper triangular matrix. When m > n, a "thin" QR yields Q of m×n and R of n×n. Householder reflections are typically preferred for dense matrices (O(2mn² - 2n³/3) flops) over the classical Gram-Schmidt due to superior numerical stability, with a backward error on the order of machine epsilon. |
Technical Features
| Category |
Algorithm |
Type of task |
Matrix Factorization |
| Computational complexity (Big O) |
O(mn²) for an m×n matrix using Householder reflections |
Spatial complexity |
O(mn) standard; can be done in-place by overwriting A with R and storing Householder vectors |
| Numerical stability |
Backward stable when using Householder reflections or Givens rotations |
Parallelizability |
Yes; blocked algorithms exist for Level-3 BLAS operations on distributed-memory systems |
| Key alternative names |
Orthogonal-triangular factorization |
Predecessor |
Gram-Schmidt orthogonalization |
| Major libraries/frameworks |
LAPACK (geqrf), NumPy (linalg.qr), MATLAB (qr), Julia (LinearAlgebra.qr) |
Referential implementation |
LAPACK's dgeqrf (Householder QR) is the de facto standard reference |
Advantages and Limitations
| Advantages |
Provides a numerically stable solution to rank-deficient least-squares problems without squaring the condition number (unlike the normal equations). The orthogonal matrix Q preserves vector norms, minimizing the amplification of rounding errors during back-substitution with R. |
| Limitations |
Computationally more expensive than LU decomposition for square systems (by a constant factor of roughly 2). Standard QR without pivoting fails to reveal the rank of a matrix; a rank-revealing QR (with column pivoting) is required, which adds computational overhead. |
Application Areas
| Product/Application area |
Solving linear least-squares problems and data fitting in scientific computing |
| Product/Application area |
Eigenvalue calculation via the QR algorithm (distinct from QR decomposition) in MATLAB and LAPACK |