linear least squares residual projection

This note is adopted from a lecture I developed for EN.530.484 at JHU

Consider the (convex) problem:

$$\theta^* = \frac{1}{2} \arg\min_\theta \|\Phi \theta - y\|^2.$$

where $\theta \in \mathbb{R}^n$, $y \in \mathbb{R}^m$. Interestingly, this problem is directly solvable through a geometric insight, and without any of the usual first-order necessary optimality conditions.

Consider the residual vector $r$

$$\Phi \theta + r = y$$

We simply need to find $\theta$ such that the residual lies completely orthogonal to the image of $\Phi$, since this is the best we can hope to do in terms of minimizing the error.

So we set $\Phi^T r = 0$.

$$\Phi^T r = \Phi^T (y - \Phi \theta) = 0 \\ \Rightarrow \theta = (\Phi^T \Phi)^{-1} \Phi y$$

which is the standard left psuedo-inverse, but without any calculus! Kind of cool.