Least Squares as Orthogonal Projection

01 An unreachable target still has a nearest reachable output

The outputs $A\theta$ fill Col(A), a finite-dimensional subspace of $\mathbb R^{m}$. Every b has a unique orthogonal projection onto that subspace. Because this projection belongs to Col(A), some coefficient vector produces it. Thus least squares always has a minimizer, even when the exact equation has none.

For the running example, $\ell = (1,-1,1)^{\mathsf T}$ satisfies $A^{\mathsf T}\ell = 0$. Every reachable output obeys $\ell ^{\mathsf T}A\theta = 0$, but $b = (1,1,1)^{\mathsf T}$ gives $\ell ^{\mathsf T}b = 1$. This certifies $b \notin \operatorname{Col}(A)$. The obstruction is a nonzero component perpendicular to the reachable plane.

$\hat\theta\in\operatorname*{arg\,min}_{\theta}\lVert A\theta-b\rVert_2^2;\quad\hat b=A\hat\theta=\operatorname{proj}_{\operatorname{Col}(A)}b$

02 The normal equations follow from the objective

Expand $f(\theta ) = (A\theta - b)^{\mathsf T}(A\theta - b) = \theta ^{\mathsf T}A^{\mathsf T}A\theta - 2b^{\mathsf T}A\theta + b^{\mathsf T}b$. $A^{\mathsf T}A$ is symmetric, so the gradient is $\nabla f(\theta ) = 2A^{\mathsf T}A\theta - 2A^{\mathsf T}b$. At a minimum, the gradient is zero, giving $A^{\mathsf T}A\hat{\theta} = A^{\mathsf T}b$.

This condition is sufficient as well as necessary: the Hessian is $2A^{\mathsf T}A$ and $z^{\mathsf T}A^{\mathsf T}Az = \Vert Az\Vert _{2}^{2} \ge 0$. The objective is convex, so a stationary point is a global minimizer. When the columns are independent, this squared length is positive for every nonzero z; the objective is strictly convex and the coefficient is unique. The geometric proof below establishes sufficiency without calculus.

$\nabla f(\hat\theta)=0\ \Longleftrightarrow\ A^{\mathsf T}(A\hat\theta-b)=0\ \Longleftrightarrow\ A^{\mathsf T}e=0$

03 A perpendicular residual proves global optimality

Suppose $A^{\mathsf T}e = 0$ with $e = b - A\hat{\theta}$. For any candidate $\theta , b - A\theta = e - A(\theta - \hat{\theta})$. The two terms are perpendicular: e is orthogonal to Col(A), while $A(\theta - \hat{\theta})$ belongs to that subspace. Pythagoras therefore splits the squared error into the best error plus a nonnegative extra term.

Equality holds precisely when $A(\theta - \hat{\theta}) = 0$. This proves both optimality and the full minimizer set $\hat{\theta} + \operatorname{Null}(A)$. For our example, $e = (1/3,-1/3,1/3)^{\mathsf T}$, so the minimum squared error is 1/3. The minimum residual length is $\sqrt{1/3}$; these are different numbers. The coefficient norm $\Vert \hat{\theta}\Vert _{2}$ is a third quantity and is not the ordinary least-squares objective.

$\lVert b-A\theta\rVert_2^2=\lVert e\rVert_2^2+\lVert A(\theta-\hat\theta)\rVert_2^2\ge\lVert e\rVert_2^2$

04 The inverse formula has a rank assumption

For $z \in \mathbb R^{n}, z^{\mathsf T}Gz = \Vert Az\Vert _{2}^{2}$. Thus $G = A^{\mathsf T}A$ is invertible exactly when $\operatorname{Null}(A) = \{0\}$, equivalently $\operatorname{rank}(A) = n$. Under this assumption $\hat{\theta} = (A^{\mathsf T}A)^{-1}A^{\mathsf T}b$ and $\hat{b} = Pb$, with $P = A(A^{\mathsf T}A)^{-1}A^{\mathsf T}$.

The normal equations remain valid when columns are dependent, but the displayed inverse does not exist. Projection onto Col(A) still exists and is unique. One can use an orthonormal basis $Q_{r}$ of its r-dimensional column space to obtain $P = Q_{r}Q_{r}^{\mathsf T}$, or write $P = AA^{+}$ using the Moore–Penrose pseudoinverse $A^{+}$. The rank-deficient code example avoids using the invalid inverse formula.

$\operatorname{rank}(A)=n\ \Rightarrow\ \text{unique }\hat\theta;\quad\operatorname{rank}(A)<n\ \Rightarrow\ \text{multiple }\hat\theta,\ \text{one }A\hat\theta$

05 QR computes the same projection with orthonormal coordinates

For full column rank, $A = QR$ with reduced Q having orthonormal columns. Split b into $QQ^{\mathsf T}b$ and its perpendicular residual. Then $\Vert A\theta - b\Vert _{2}^{2} = \Vert R\theta - Q^{\mathsf T}b\Vert _{2}^{2} + \Vert (I - QQ^{\mathsf T})b\Vert _{2}^{2}$. The second term cannot be changed by $\theta$; the first becomes zero when $R\hat{\theta} = Q^{\mathsf T}b$.

This gives the same fitted output $QQ^{\mathsf T}b$ as the Gram-matrix formula. In this example Q is 3 × 2, so $Q^{\mathsf T}Q = I_{2}$, while $QQ^{\mathsf T}$ is a rank-two projection in $\mathbb R^{3}$. Different sign choices for columns of Q and matching rows of R leave QR and $QQ^{\mathsf T}$ unchanged.

$R\hat\theta=Q^{\mathsf T}b;\quad A\hat\theta=QR\hat\theta=QQ^{\mathsf T}b=Pb$

06 Distinguish a linear subspace from a shifted tangent plane

Printed slide 33 projects $s = (2,3,0)^{\mathsf T}$ onto the tangent plane through $p_{0} = (1,2,-1)^{\mathsf T}$. That plane is $p_{0} + \operatorname{Col}(A)$. First use the displacement $b = s - p_{0} = (1,1,1)^{\mathsf T}$, which is exactly the target in our least-squares example.

$Pb = (2/3,4/3,2/3)^{\mathsf T}$ is the projected displacement. To recover the projected point in the original coordinates, add $p_{0}: \hat{s} = p_{0} + Pb = (5/3,10/3,-1/3)^{\mathsf T}$. The projection onto the shifted plane is an affine map of s; P itself projects onto the subspace through the origin.

$\hat s=p_0+P(s-p_0);\quad s-\hat s=b-Pb=e$

07 Use the formulas to understand the problem and a solver to compute it

The Gram-matrix step exposes the lecture’s normal equations and uses np.linalg.solve(G, h) rather than explicitly computing $G^{-1}$. Forming $A^{\mathsf T}A$ can worsen conditioning: for full column rank, its spectral condition number is the square of A’s. Solving with G instead of inverting it does not remove that effect. The small well-conditioned example is suitable for inspecting the formula.

For general data, use np.linalg.lstsq(A, b, rcond=None), which works directly with A and supports rank-deficient systems. It returns a minimum-Euclidean-norm coefficient if minimizers are not unique. The rank cutoff depends on singular values and numerical precision, so near-dependent columns require attention to scale and tolerance. An approximately zero $A^{\mathsf T}e$ checks stationarity to the chosen tolerance; the algebra above proves optimality.