Least Squares and QR

Summary

When $A\mathbf{x}=\mathbf{b}$ is inconsistent, least squares finds $\hat{\mathbf{x}}$ minimizing $\parallel A\mathbf{x}-\mathbf{b}\parallel$ . The residual is orthogonal to $\mathrm{Col}(A)$ . QR factorization provides a stable way to compute $\hat{\mathbf{x}}$ without forming $A^{T}A$ explicitly in unstable ways.

Prerequisites

Orthogonality and Projections, Matrices and Row Reduction, Systems of Linear Equations. Hub: Linear Algebra.

Definition / Statement

Given $A\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$ , a least-squares solution is any $\hat{\mathbf{x}}\in {\mathbb{R}}^n$ minimizing

If the columns of $A$ are linearly independent, $\hat{\mathbf{x}}$ is unique and satisfies the normal equations

A QR factorization of full-column-rank $A$ writes

where $Q\in {\mathbb{R}}^{m\times n}$ has orthonormal columns ( $Q^{T}Q=I_n$ ) and $R\in {\mathbb{R}}^{n\times n}$ is upper triangular and invertible.

Objects and Dimensions

Notation

Conditions / Assumptions

• Prefer the Euclidean norm (least squares = $L^2$ ).
• Unique $\hat{\mathbf{x}}$ when $\mathrm{rank}(A)=n$ (full column rank), so $A^{T}A$ is invertible.
• If columns are dependent, least-squares solutions still exist but are not unique; use pseudoinverse or additional constraints.
• QR assumes full column rank for the thin $R$ to be invertible.

Matrix / Vector Form

Normal equations

Geometry: $A\hat{\mathbf{x}}={\mathrm{proj}}_{\mathrm{Col}(A)}\mathbf{b}$ and $A^T(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}$ .

Via QR ( $A=QR$ ):

(solve by forward/back substitution on the triangular system).

Procedure

1. Check whether $A\mathbf{x}=\mathbf{b}$ is consistent; if not, use least squares.
2. If using normal equations: form $A^{T}A$ and $A^T\mathbf{b}$ , solve the $n\times n$ system (watch conditioning).
3. If using QR: factor $A=QR$ (Gram–Schmidt, Householder, or library routine), solve $R\hat{\mathbf{x}}=Q^T\mathbf{b}$ .
4. Report residual norm $\parallel \mathbf{b}-A\hat{\mathbf{x}}\parallel$ as a fit diagnostic.

Worked Example

Fit a line $y=c_0+c_{1}x$ through points $(0,1)$ , $(1,1)$ , $(2,3)$ in the least-squares sense.

Solve $\left(\begin{array}{cc}3& 3\\ 3& 5\end{array}\right)\left(\begin{array}{c}{c}_0\\ c_1\end{array}\right)=\left(\begin{array}{c}5\\ 7\end{array}\right)$ :
subtract first equation from second after scaling gives $2c_1=2$ , so $c_1=1$ , then $3c_0+3=5$ , so $c_0=\frac{2}{3}$ .

Model: $y=\frac{2}{3}+x$ .

Common Mistakes

• Minimizing $\parallel A^T\mathbf{x}-\mathbf{b}\parallel$ instead of $\parallel A\mathbf{x}-\mathbf{b}\parallel$ .
• Using $A^{-1}$ when $A$ is not square.
• Ignoring rank deficiency when $A^{T}A$ is singular.
• Forgetting that least squares yields the projection of $\mathbf{b}$ onto $\mathrm{Col}(A)$ , not necessarily $\mathbf{b}$ itself.

Connections

• Related: Orthogonality and Projections, Matrices and Row Reduction, Systems of Linear Equations
• Applied statistics/numerics: Least Squares when present under numerical methods
• Next: applications in regression and numerical linear algebra under Numerical Methods

References

Least squares and QR as in MIT 18.06.^[1]