Lesson 5.6: The QR Decomposition (The Stable Masterpiece)

The numerically stable and elegant method for solving least squares problems.

We stand at a crossroads. We have a powerful theoretical solution to the least squares problem—the Normal Equations—but we know it can be a numerically unstable computational method. We also have a powerful tool for building a perfect, stable basis—the Gram-Schmidt process.

Today, we unite these ideas. The QR Decomposition is not just another factorization; it is the direct embodiment of the Gram-Schmidt process as a matrix product. It is the professional, stable, and elegant method for solving least squares and many other problems in linear algebra.

What is QR Decomposition? The Geometric View

The decomposition `A = QR` says: "Any matrix `A` can be represented as a different set of perfectly orthonormal axes (`Q`), followed by a simple set of scaling and shearing instructions (`R`) that tells you how to rebuild the original skewed vectors from these perfect axes."

`Q` (The Orthonormal Basis): This is an Orthogonal Matrix. Its columns are $\{q_1, q_2\}$ - the "perfect" orthonormal basis for the Column Space of `A`. We find `Q` using the Gram-Schmidt process.
`R` (The Recipe Matrix): This is an Upper Triangular Matrix. It is the "recipe" that tells us how to construct the original columns of `A` as linear combinations of the new `q` vectors.

Building `A=QR`: The Mechanics of `R`

The entries of `R` are the coefficients and lengths we calculate during the Gram-Schmidt process. The relationship `A = QR` for `A = [v₁ | v₂]` means:

\begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Expanding this gives us:

$v_1 = r_{11}q_1$
$v_2 = r_{12}q_1 + r_{22}q_2$

The entries of `R` are the dot products of the original columns with the new orthonormal vectors:

R = Q^T A = \begin{bmatrix} q_1^T \\ q_2^T \end{bmatrix} \begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} q_1^Tv_1 & q_1^Tv_2 \\ q_2^Tv_1 & q_2^Tv_2 \end{bmatrix}

Because of how Gram-Schmidt works (`q₂` is orthogonal to `v₁`'s original space), `q₂ᵀv₁` will be 0, making `R` upper triangular.

The Payoff: Solving Least Squares without `AᵀA`

We want to solve `AᵀAx̂ = Aᵀb`. By substituting `A = QR`:

(QR)^T(QR)\hat{x} = (QR)^T b

This simplifies using `QᵀQ = I`:

R^T Q^T Q R \hat{x} = R^T Q^T b \implies R^T R \hat{x} = R^T Q^T b

The Golden Equation

Since `Rᵀ` is invertible, we can cancel it from both sides, leaving the stunningly simple and stable result:

R\hat{x} = Q^Tb

This is the golden equation for solving least squares. It is theoretically identical to the Normal Equations but computationally far superior because it avoids forming the ill-conditioned `AᵀA` matrix.

The Complete Algorithm (The Professional's Method)

Decompose A into QR:
- Take the columns of `A`.
- Use the Gram-Schmidt process to find the orthonormal vectors `qᵢ`. These form the columns of `Q`.
- The matrix `R` can then be calculated as `R = QᵀA`.
Compute the target vector: Calculate the new, smaller target vector `Qᵀb`.
Solve for `x̂`: Solve the simple upper triangular system `Rx̂ = Qᵀb` using fast and easy back substitution.

Lesson 5.5: The Stable Solution: The Gram-Schmidt Process

Lesson 6.1: The Singular Value Decomposition (SVD)