Projection & Least Squares

The least-squares problem $\min_w \Vert Xw - y \Vert^2$ is, geometrically, an orthogonal projection: when $y \notin C(X)$ no exact solution exists, and the optimum requires $Xw$ to equal the orthogonal projection $\hat{y} = Py$ of $y$ onto the column space $C(X)$, with residual $r = y - Xw$ orthogonal to $C(X)$, i.e. $X^T(y - Xw) = 0$, giving the normal equations $X^TXw = X^Ty$; with full column rank, $w = (X^TX)^{-1}X^Ty$. The projection matrix $P = X(X^TX)^{-1}X^T$ is idempotent ($P^2 = P$) and symmetric ($P^T = P$), and $I - P$ projects onto $N(X^T)$. When $X$ is rank-deficient or $X^TX$ ill-conditioned, use the pseudoinverse $X^+ = V\Sigma^+U^T$ (from the SVD; $\Sigma^+$ inverts nonzero singular values), giving the minimum-norm solution $w = X^+y$.

closed-form solution of linear regression; line/polynomial fitting; recommenders, signal estimation, and solving overdetermined systems; the fallback when $X^TX$ fails due to collinearity or high dimensionality; also the starting point of Ridge regularization ($X^TX + \lambda I$).

with more equations than unknowns, $y$ typically lies outside $C(X)$ and the system has no solution; the projection theorem guarantees that $\hat{y}$, with residual orthogonal to the column space, is the unique best approximation in the Euclidean norm; when $X$ is rank-deficient, $(X^TX)^{-1}$ does not exist and the pseudoinverse degenerates to the minimum-norm solution; moreover the normal equations square the condition number ($\kappa(X^TX) = \kappa(X)^2$), so the pseudoinverse/QR/SVD route is numerically far more stable.

Derivation: from the residual orthogonality $X^T(y - Xw) = 0$, derive the normal equations $w = (X^TX)^{-1}X^Ty$ and sketch the projection geometry.

Prove $P = X(X^TX)^{-1}X^T$ is an orthogonal projection ($P^2 = P$, $P^T = P$); onto which subspace does $I - P$ project?

By hand: fit a line $y = w_0 + w_1x$ to 3 data points by constructing $X$ and $y$ and solving the normal equations.

When is $X^TX$ singular? How does the pseudoinverse $X^+ = V\Sigma^+U^T$ yield the minimum-norm solution, and how does it differ from $(X^TX)^{-1}X^T$?

Why are the normal equations numerically unstable ($\kappa(X^TX) = \kappa(X)^2$)? How do pseudoinverse, regularization, or QR mitigate collinearity?