QR and Least Squares Problems
What You'll Learn
You'll learn how to solve overdetermined least squares problems efficiently using QR decomposition, bypassing the potential numerical issues of normal equations.
The Challenge with Normal Equations
When solving the least squares problem Ax = b (where A has more rows than columns), we've previously used the normal equations: AᵀAx = Aᵀb. While mathematically correct, forming AᵀA can amplify numerical errors because it roughly squares the condition number of A, making the problem more sensitive to rounding errors.
The QR Approach: A Better Path
If A = QR (where Q has orthonormal columns and R is upper triangular), we can bypass the normal equations entirely.
Here's why this works: The least squares solution minimizes ||Ax - b||. Since Q has orthonormal columns, multiplying by Qᵀ preserves distances (it's an isometry). Therefore:
||Ax - b|| = ||QRx - b|| = ||Rx - Qᵀb||
Now we just need to minimize ||Rx - Qᵀb||, which means solving the simpler triangular system:
Rx = Qᵀb
The Algorithm
- Compute the QR decomposition: A = QR
- Multiply: c = Qᵀb
- Solve the triangular system Rx = c using back-substitution
This avoids forming AᵀA entirely, maintaining better numerical stability while being computationally efficient.
Why It's Better
Think of AᵀA as taking a photograph of a photograph—quality degrades. The QR method works with the "original image" (A itself), preserving accuracy. You get the same mathematical answer but with significantly better numerical behavior, especially when A is ill-conditioned.
Key Takeaway: Using QR decomposition to solve least squares problems (Rx = Qᵀb) is numerically superior to normal equations because it avoids squaring the condition number and works directly with the original matrix structure.