# 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.

• Can you recall what mean "fat" and "full raw rank" for matrices. Not easy to find the definitions on the Internet. – mathcounterexamples.net Jun 10 '15 at 19:29
• fat here means number of column > number of row. full row rank means $A$'s all rows are linearly independent. – sleeve chen Jun 10 '15 at 19:32
• – copper.hat Jun 10 '15 at 19:56

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)$$
• How to get $x - z + A^T\lambda$? Do you form the Lagrangian and take the gradient of Lagrangian with respect to $x$ and get $x - z + A^T\lambda$? – sleeve chen Jun 10 '15 at 19:47
• Exactly, the Lagrangian is $\frac12\|x-z\|^2 + \lambda^T(Ax-b)$. – daw Jun 10 '15 at 19:48
• This also follows from linear algebra, since at the optimum, you have $x-z \bot \ker A$. – copper.hat Jun 10 '15 at 19:57
• @daw Additional question, you solve $x-z+A^T\lambda=0$ for $\lambda$ instead of $x$ and at last you can find $x$ why? Because of KKT? primal optimal = dual optimal? I am a little bit confused about this. thx! – sleeve chen Jun 10 '15 at 20:14
• I use the equation twice: first to get $\lambda$ (while applying $Ax=b$), second to get $x$. – daw Jun 10 '15 at 20:39