7.1012 min read

QR Factorization for Least Squares

Solving the normal equations $A^T A \hat{x} = A^T b$ directly can be numerically unstable: squaring $A$ can double the condition number. The preferred approach factors $A$ into $A = QR$ , where $Q$ has orthonormal columns and $R$ is upper triangular.

QR factorization via Gram-Schmidt orthogonalization: start with the columns $a_1, \ldots, a_n$ of $A$ . Successively subtract projections to make them orthogonal, then normalize. The orthonormal set forms the columns of $Q$ , and the coefficients form $R$ .

Once $A = QR$ , the least squares problem simplifies beautifully: $\|b - Ax\|^2 = \|b - QRx\|^2$ . Substituting $Q^T Q = I$ : $\|Q^T b - Rx\|^2 + \|b - QQ^T b\|^2$ . The first term is minimized by solving the upper triangular system $R\hat{x} = Q^T b$ via back-substitution.

Compared to the normal equations, QR is numerically superior: $Q$ is orthogonal so squaring is avoided, and back-substitution on $R$ is stable. For this reason, most software (NumPy, MATLAB) uses QR under the hood for lstsq.

Formal View

Theorem 7.10 — QR Least Squares

A = QR

where

Q \in \mathbb{R}^{m \times n}

has orthonormal columns and

R \in \mathbb{R}^{n \times n}

is upper triangular with positive diagonal, then the unique least squares solution (when

A

has full column rank) is

\hat{x} = R^{-1} Q^T b,

equivalently obtained by solving

R\hat{x} = Q^T b

via back-substitution.

Definition 7.10 — QR Factorization

Every matrix

A \in \mathbb{R}^{m \times n}

with

m \geq n

and full column rank can be written

A = QR

where

Q \in \mathbb{R}^{m \times n}

satisfies

Q^T Q = I_n

(orthonormal columns) and

R \in \mathbb{R}^{n \times n}

is upper triangular with positive diagonal entries. This is the reduced (thin) QR factorization.

The Gram-Schmidt process constructs Q and R column by column. Modified Gram-Schmidt is numerically more stable than classical Gram-Schmidt.

Interactive Visualization

Least Squares Fitting

Why This Matters

QR factorization is the standard algorithm for solving least squares problems in scientific computing.

Numerical linear algebra: `numpy.linalg.lstsq` uses QR internally
Signal processing: QR-based adaptive filtering (RLS algorithm)
Machine learning: QR decomposition is used in Gram-Schmidt orthogonalization of attention heads
Eigenvalue algorithms: the QR algorithm iterates QR factorizations to find eigenvalues

Learning Resources

Gram-Schmidt and QR Factorization

MIT OpenCourseWare

Strang derives Gram-Schmidt orthogonalization and builds the QR factorization.

49 min

QR Decomposition (for least squares)

3Blue1Brown

Visual explanation of why QR is better than normal equations numerically.

10 min

Quiz

Question 1

In the QR decomposition $A = QR$ , which property does $Q$ have?

Question 2

Using QR, the least squares solution satisfies:

Question 3

QR factorization is preferred over normal equations for numerical stability.

Common Mistakes

Confusing the QR algorithm for eigenvalues with QR factorization for least squares — they both use QR but for different purposes.
Assuming $Q^T = Q^{-1}$ requires $Q$ to be square — the reduced QR only gives $Q^T Q = I_n$ (not $Q Q^T = I_m$ ).
Skipping QR and always using normal equations — fine for small problems but numerically dangerous for nearly rank-deficient $A$ .