# Prove That Projection Operator Is Non Expansive

I am trying to prove that the projection operator defined as: $$$$P(z) := argmin_{x \in \mathcal{C}} \frac{1}{2}\|x-z\|^2_2$$$$ is non-expansive. Here $$\mathcal{C}$$ is nonempty closed and convex set. To show this, I proceed as: $$$$\|P(z_1) - P(z_2)|| =\|x_1-x_2\|$$$$ , 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?

• What is $C$? This is not true in general for arbitrary set $C$ but holds e.g. for $C$ convex.
– air
Sep 8, 2015 at 7:38
• Assume $C$ is convex.
– CKM
Sep 8, 2015 at 8:23
• 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$. Sep 8, 2015 at 23:34
• Thanks for clarifying. Do you have proof for this?
– CKM
Sep 9, 2015 at 8:04
• @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? Nov 11, 2015 at 14:54

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}

• 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?
– CKM
Sep 8, 2015 at 9:31
• 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/…)
– air
Sep 8, 2015 at 14:53
• Did the asker forget to accept @air's answer (it completely answers the question as it stands) ? Nov 12, 2015 at 7:58
• FWIW: That variational characterization is called the Bourbaki-Cheney-Goldstein inequality. Nov 12, 2015 at 7:58
• Can you explain how the adding/rearranging works? I just cannot see it, even after 2 hours. Feb 18, 2019 at 2:46