3
$\begingroup$

I am trying to prove that the projection operator defined as: \begin{equation} P(z) := argmin_{x \in \mathcal{C}} \frac{1}{2}\|x-z\|^2_2 \end{equation} is non-expansive. Here $\mathcal{C}$ is nonempty closed and convex set. To show this, I proceed as: \begin{equation} \|P(z_1) - P(z_2)|| =\|x_1-x_2\| \end{equation} , where $x_1, x_2$ are points in the set $\mathcal{C}$. Now, I know that $\|x_1-x_2\| \leq \|z_1-z_2\|$. But, how to prove this last part? Can JL lemma be used someway?

$\endgroup$
  • $\begingroup$ What is $C$? This is not true in general for arbitrary set $C$ but holds e.g. for $C$ convex. $\endgroup$ – air Sep 8 '15 at 7:38
  • $\begingroup$ Assume $C$ is convex. $\endgroup$ – chandresh Sep 8 '15 at 8:23
  • $\begingroup$ The projection operator onto a convex set is more than just non-expansive, it is in fact firmly non-expansive, i.e $\|P(z_1) - P(z_2)\|^2 + \|Q(z_1) - Q(z_2)\|^2 \le \|z_1 - z_2\|^2$ $\forall (z_1, z_2) \in \mathcal{X}^2$, where $Q := Id - P$. $\endgroup$ – dohmatob Sep 8 '15 at 23:34
  • $\begingroup$ Thanks for clarifying. Do you have proof for this? $\endgroup$ – chandresh Sep 9 '15 at 8:04
  • $\begingroup$ @dohmatob -- What you wrote is true when $P$ is linear, but for the general case, when $C$ is just convex and no a subspace, I am not sure it is true. Can you prove it? $\endgroup$ – uniquesolution Nov 11 '15 at 14:54
4
$\begingroup$

As in your post, let $z_1$, $z_2$ be arbitrary points.

Recall the variational characterization of the projection operator onto nonempty, closed, convex sets:

$$ \langle z_1 - P(z_1), x- P(z_1) \rangle\leq 0 \; \forall \; x \in C $$

Now also notice that by definition $P(z_2) \in C$ thus we get:

$$ \langle z_1 - P(z_1), P(z_2)- P(z_1) \rangle\leq 0 $$

Similarly we also get:

$$ \begin{aligned} &\langle z_2 - P(z_2), P(z_1)- P(z_2) \rangle\leq 0 \\ \Rightarrow &\langle P(z_2) - z_2, P(z_2)- P(z_1) \rangle\leq 0 \end{aligned} $$

Adding these two inequalities, rearranging and finally applying the Cauchy-Schwarz inequality, we get:

$$ \begin{aligned} \langle P(z_2) - P(z_1), P(z_2)- P(z_1) \rangle &\leq \langle z_2 - z_1, P(z_2)- P(z_1) \rangle \\ & \leq \vert\vert z_2 - z_1 \vert\vert \; \vert\vert P(z_2) - P(z_1) \vert\vert \end{aligned} $$

Thus:

$$ \begin{aligned} &\vert\vert P(z_2) - P(z_1) \vert\vert^2 \leq \vert\vert z_2 - z_1 \vert\vert \; \vert\vert P(z_2) - P(z_1) \vert\vert \\ \Rightarrow &\vert\vert P(z_2) - P(z_1) \vert\vert \leq \vert\vert z_2 - z_1 \vert\vert \end{aligned} $$

$\endgroup$
  • $\begingroup$ Thanks. That makes sense. One small thing. I wanted to read more about variational characterization of the projection operator. Is there any any source or link? $\endgroup$ – chandresh Sep 8 '15 at 9:31
  • $\begingroup$ Sometimes it is called the Projection theorem, you can find it in many more theoretical convex analysis books (e.g. Proposition 1.1.9 in the book Convex Optimization Theory by Dimitri Bertsekas). He also has some slides from his lectures at MIT OCW, see the 5th slide (ocw.mit.edu/courses/electrical-engineering-and-computer-science/…) $\endgroup$ – air Sep 8 '15 at 14:53
  • $\begingroup$ Did the asker forget to accept @air's answer (it completely answers the question as it stands) ? $\endgroup$ – dohmatob Nov 12 '15 at 7:58
  • 1
    $\begingroup$ FWIW: That variational characterization is called the Bourbaki-Cheney-Goldstein inequality. $\endgroup$ – dohmatob Nov 12 '15 at 7:58
  • $\begingroup$ Can you explain how the adding/rearranging works? I just cannot see it, even after 2 hours. $\endgroup$ – mavavilj Feb 18 at 2:46

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.