# Projection of $z$ onto the affine set $\{x\mid Ax = b\}$

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.

#### Solutions Collecting From Web of "Projection of $z$ onto the affine set $\{x\mid Ax = b\}$"

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)$$