Skip to main content

Projections, Least Squares, and QR Turn Inconsistency into Best Approximation

What This Concept Is​

Many real systems are inconsistent: the observation vector $b$ does not lie in the column space of $A$, so $Ax = b$ has no exact solution. Instead of accepting "no solution," the least-squares approach replaces the impossible goal "solve exactly" with the right goal "minimize error in the 2-norm."

Given $Ax = b$ with no exact solution, least squares chooses $\hat x$ to minimize $|Ax - b|^2$. Geometrically, $A\hat x$ is the orthogonal projection of $b$ onto $\text{Col}(A)$. The residual $r = b - A\hat x$ lies in $\text{Col}(A)^\perp = \text{Null}(A^T)$. The orthogonality condition $A^T r = 0$ immediately yields the normal equations

$$A^T A,\hat x = A^T b.$$

When $A$ has independent columns, $A^TA$ is symmetric positive definite, so the normal equations have a unique solution $\hat x = (A^TA)^{-1}A^T b$. The matrix $(A^TA)^{-1}A^T$ is the left pseudoinverse $A^+$; the projection onto $\text{Col}(A)$ is $P = A(A^TA)^{-1}A^T$. Important properties: $P^2 = P$ (idempotent), $P^T = P$ (symmetric), and $Pb = A\hat x$.

QR factorization avoids explicitly forming $A^TA$. For full column rank with m>=n, write $A=QR$ with orthonormal columns in Q and nonsingular upper-triangular R. Minimize the squared residual by solving $R\hat x=Q^Tb$. In the 2-norm $\kappa_2(A^TA)=\kappa_2(A)^2$, while Q preserves the singular values of R. QR avoids this additional Gram-matrix conditioning; it does not make the original least-squares problem well-conditioned. Sensitivity to changes in A can also depend on the residual. See the LAPACK error analysis.

Distinguish three solution regimes for $Ax = b$:

  • Square, full rank: $\hat x = A^{-1}b$, exact. Solve by LU.
  • Overdetermined ($m > n$), full column rank: $\hat x$ is the least-squares solution. Solve by QR.
  • Rank less than the number of columns: infinitely many least-squares coefficient vectors, all giving the same fitted vector. The minimum-norm one is $\hat x = A^+ b$, computed by SVD.

Why It Matters Here​

This is one of the most important pages in the module because it connects orthogonality, approximation, regression, data fitting, and numerical stability. If you want the first serious bridge from textbook linear algebra to ML and data work, this is it. Ordinary linear least squares is one regression objective; absolute-error, constrained and regularized fits are different optimization problems. A principal-component projection is orthogonal after specifying centering and the metric.

Projections also underlie the geometry of "best explanation" in approximation theory. The orthogonality of the residual means the least-squares estimator extracts everything the columns of $A$ can explain about $b$ and leaves behind a residual that the model provably cannot touch.

Concrete Examples​

Example 1 -- projection onto a line. Project $b = (3, 1)^T$ onto the line spanned by $a = (1, 2)^T$. The projection coefficient is $\hat x = \tfrac{a^T b}{a^T a} = \tfrac{3 + 2}{1 + 4} = 1$. The projection is $\hat x \cdot a = (1, 2)^T$. The residual $r = b - \hat x a = (2, -1)^T$. Verify orthogonality: $a^T r = 2 - 2 = 0$. This is least squares in one dimension.

Example 2 -- line of best fit. Fit $y = c + mx$ through the three points $(0, 1), (1, 2), (2, 2)$. Set up

$$A = \begin{pmatrix} 1 & 0 \ 1 & 1 \ 1 & 2 \end{pmatrix}, \quad b = \begin{pmatrix} 1 \ 2 \ 2 \end{pmatrix}.$$

Then

$$A^T A = \begin{pmatrix} 3 & 3 \ 3 & 5 \end{pmatrix}, \quad A^T b = \begin{pmatrix} 5 \ 6 \end{pmatrix}.$$

Solve $\begin{pmatrix} 3 & 3 \ 3 & 5 \end{pmatrix}\begin{pmatrix} c \ m \end{pmatrix} = \begin{pmatrix} 5 \ 6 \end{pmatrix}$. Subtract row 1 from row 2: $2m = 1$, so $m = 0.5$, $c = (5 - 3\cdot 0.5)/3 = 7/6$. Best-fit line: $y = 7/6 + 0.5 x$. Residual: $b - A\hat x = (1, 2, 2)^T - (7/6, 5/3, 13/6)^T = (-1/6, 1/3, -1/6)^T$. Check $A^T r = 0$: sum of residuals is $0$, and sum of $x_i r_i$ is $0$. Orthogonality confirmed.

Example 3 -- QR version of the same fit. Apply Gram-Schmidt to columns of $A$: $q_1 = (1, 1, 1)^T / \sqrt{3}$. Project column 2 onto $q_1$: coefficient $(0 + 1 + 2)/\sqrt{3} = 3/\sqrt{3} = \sqrt{3}$. Subtract: $(0, 1, 2)^T - \sqrt{3}\cdot q_1 = (-1, 0, 1)^T$. Normalize: $q_2 = (-1, 0, 1)^T/\sqrt{2}$. So

$$Q = \begin{pmatrix} 1/\sqrt{3} & -1/\sqrt{2} \ 1/\sqrt{3} & 0 \ 1/\sqrt{3} & 1/\sqrt{2} \end{pmatrix}, \quad R = \begin{pmatrix} \sqrt{3} & \sqrt{3} \ 0 & \sqrt{2} \end{pmatrix}.$$

Compute $Q^T b = (5/\sqrt{3}, 1/\sqrt{2})^T$. Back-solve $R\hat x = Q^T b$: from row 2, $m = (1/\sqrt{2})/\sqrt{2} = 1/2$; from row 1, $\sqrt{3} c + \sqrt{3}\cdot(1/2) = 5/\sqrt{3}$, so $c = 7/6$. Same answer, obtained without forming $A^T A$ explicitly.

Common Confusion / Misconceptions​

"Least squares fixes inconsistency by secretly making the equations true." It does not. It finds the best approximation $A\hat x$ within $\text{Col}(A)$ under a squared-error criterion. The equations remain inconsistent; only the residual norm is minimized.

"Normal equations guarantee the same numerical accuracy as QR." Forming the Gram matrix squares the 2-norm condition number for full column rank. This increases risk of rounding-related accuracy loss, but does not predict an exact number of lost digits on every input. Truncating singular values changes the fitted model and must be reported.

"Projection matrices are invertible." A projection $P$ onto a proper subspace satisfies $P^2 = P$ and has eigenvalues $0$ and $1$ only. It is singular (because of the $0$ eigenvalues on the complement). Idempotence replaces invertibility as the defining algebraic property.

"Least squares requires Gaussian noise." No. Least squares minimizes $|Ax - b|_2^2$ as an approximation criterion, independent of probability. Under independent Gaussian errors of common variance, minimizing unweighted squared error gives a maximum-likelihood coefficient estimate, but the geometric projection argument needs no probabilistic assumption.

How To Use It​

When faced with too many equations:

  1. Interpret the system as $b$ trying to land inside $\text{Col}(A)$. If $b \in \text{Col}(A)$, solve exactly; otherwise proceed.
  2. Project $b$ onto $\text{Col}(A)$; the image is $A\hat x$.
  3. Derive the optimality condition $A^T r = 0$ from orthogonality of the residual.
  4. Prefer QR (or SVD) to normal equations whenever conditioning is a concern.
  5. Extract the residual and its norm; report both. Residual norm tells you how good the approximation is.
  6. If $A$ is rank-deficient, switch to the minimum-norm solution via SVD.

A library least-squares routine may return squared residual sums rather than a residual vector or norm, and some return an empty residual array in rank-deficient or non-tall cases. Read its return contract and compute b−Ax explicitly when needed. The offline kit returns a vector, its 2-norm and A^T times that vector with documented meanings.

Transfer to the calibration project​

Use this concept to justify a result or reject an assumption in the calibration project. Name the matrix shape, objective, scalar field and available evidence before interpreting the result.

Check Yourself​

  1. Why must the residual be orthogonal to the column space at the optimum?
  2. What does $A^T A$ represent geometrically?
  3. Why is QR often preferred over explicitly forming normal equations?
  4. What is the geometric meaning of the projection matrix $P$, and why does $P^2 = P$?
  5. When does least squares have a unique solution, and when does it have infinitely many?
  6. Why is a small residual not the same as a small error in the parameters $x$?

Mini Drill or Application​

  1. Project $b = (3, 1)^T$ onto the line spanned by $a = (1, 2)^T$. Verify the residual is orthogonal to $a$.
  2. Set up and solve the least-squares problem for fitting $y = c + mx$ to the points $(0, 1), (1, 2), (2, 2)$. Report $(c, m)$, the residual vector, and the residual norm.
  3. In NumPy: x, residuals, rank, sv = np.linalg.lstsq(A, b, rcond=None). Use the $A$ and $b$ from the previous drill. Compare x to your hand answer.
  4. Implement Gram-Schmidt on the same $A$ to compute $Q$ and $R$; solve $R\hat x = Q^T b$ by back-substitution; confirm the answer matches.
  5. Write in one sentence why the squared 2-norm, rather than the 1-norm or $\infty$-norm, produces the clean orthogonality geometry used above. (Hint: differentiate the 1-norm at a sign change.)

Read This Only If Stuck​

Use the bounded reading guide and the Strang book index. The book link opens an index; find the named topic in your edition, read a small section and reconstruct one argument with the book closed.

Prove optimality without assuming unique coefficients​

Let p=A*x-hat and r=b−p satisfy A^T r=0. For any correction h, ||b−A(x-hat+h)||²=||r||²+||Ah||² because the cross term is zero. Thus x-hat minimizes squared error. Fitted p is unique, but any h in Null(A) gives the same fit and can change the coefficients.

For a design with columns a and 2a, only x_1+2x_2 is identifiable. An SVD pseudoinverse selects the coefficient vector orthogonal to the nullspace. Weighted least squares changes the inner product; ridge adds a penalty and its residual is generally not orthogonal under the original criterion. Transfer: P9 and P19; record each changed objective explicitly.

After an independent attempt, use practice feedback and model contracts to check your reasoning.