Orthogonal Projection of $ z $ onto the Affine set $ \left\{ x \mid A x = b \right\} $

Suppose $A$ is fat(number of columns > number of rows) and full row rank. The projection of $z$ onto $\{x\mid Ax = b\}$ is (affine)

$$P(z) = z - A^T(AA^T)^{-1}(Az-b)$$

How to show this?

Note: $A^T(AA^T)^{-1}$ is the pseudo-inverse of $A$

What I am thinking is from:

1. Least square problem: $$\text{min $\left\|\: Ax-b \,\right\|_2$}$$
   The solution for this is $\hat{x} = A^T(AA^T)^{-1}b$. It seems $(Az - b )$ above is the role of $b$ here.

2. Vector projection of $x$ onto $y$: $$p = \frac{x^Ty}{y^Ty}y$$

But I still cannot figure out how to prove the above result.

Solution 1:

The projection of $z$ onto the set $\{x:\ Ax=b\}$ is given by the solution of $$ \min \frac12\|x-z\|^2 \quad \text{ subject to } Ax=b. $$ The KKT system is a necessary (since constraints are linear) and sufficient (since this is a convex problem): $$ Ax=b, \quad x-z +A^T\lambda = 0. $$ Multiply the second equation by $A$, solve for $\lambda$: $\lambda=(AA^T)^{-1}(Az-b)$, plug this again into the second equation to obtain $$ x = z - A^T\lambda =z-A^T (AA^T)^{-1}(Az-b) $$