subspace constraint minimization

Question

The problem is minimize over all $\theta \in \mathbb{R}^n$

$$\frac{1}{2} ||Y - \theta||^2$$ subject to $A \theta = 0$ where $A$ is $m \times n$.

Let $\theta^*$ be the solution. My notes seem to suggest $$\theta^* = (I - A'(AA')^{-1} A)Y = (I - P)Y$$

where $P = A'(AA')^{-1} A $ is being referred to as the projection matrix.

If $P$ is projection into, maybe $\ker$ $A$, then $\theta^*$ should be $PY$. But since $\theta^* = Y - YP$, this suggests $P$ is projection into $(\ker A)^\perp$.

Can someone prove this? Or in general prove why $\theta^* = (I - P)Y$?

Answer 1

Another way to phrase the question is to find which vector in the subspace $V=\ker A$ is closest to the vector $Y\in \mathbb R^n$.

Suppose we can find $v\in V$ such that $Y-v$ is orthogonal to the subspace $V$. Then by the pythagorean theorem, for any vector $w\in V$ we would have $$ \|w-Y\|^2=\|(w-v)+(v-Y)\|^2=\|w-v\|^2+\|v-Y\|^2\geq \|v-Y\|^2, $$ and since equality is attained when $w=v$ it follows that $v$ would be the closest vector to $Y$ that lies in $V$.

The mapping sending $Y$ to $v$ is exactly what is meant by "orthogonal projection": it is a linear operation, and thus can be represented by a matrix, with the explicit formulas you have written down. If you are looking for a proof of such formulas, it can be achieved using a judicious chose of basis.

Answer 2

I was able to solve this using Lagrangian, $L(\theta) = \frac{1}{2} ||Y - \theta||^2 + \lambda^T A \theta$

$\nabla_\theta L(\theta) = 0$ $\implies $ $\theta^* = Y - A^T \lambda$

Using $A \theta^* = 0$ $\implies $ $\lambda = (A A')^{-1} A Y$

giving me $\theta^* = Y - A'(AA')^{-1} AY$.

But I still want to confirm/refute my intuition that $P = A'(AA')^{-1} A $ is projection onto $(\ker A)^\perp$. Anyone is welcome to explain.