[Math] Prove That Projection Operator Is Non Expansive

Question

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?

Answer 1

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