10
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – sleeve chen Jun 10 '15 at 19:47
  • 1
    $\begingroup$ Exactly, the Lagrangian is $\frac12\|x-z\|^2 + \lambda^T(Ax-b)$. $\endgroup$ – daw Jun 10 '15 at 19:48
  • 1
    $\begingroup$ This also follows from linear algebra, since at the optimum, you have $x-z \bot \ker A$. $\endgroup$ – copper.hat Jun 10 '15 at 19:57
  • $\begingroup$ @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! $\endgroup$ – sleeve chen Jun 10 '15 at 20:14
  • 1
    $\begingroup$ I use the equation twice: first to get $\lambda$ (while applying $Ax=b$), second to get $x$. $\endgroup$ – daw Jun 10 '15 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.