0
$\begingroup$

Let $K\subset\mathbb{R}^n$ be a non-empty convex set. Let $\pi_K$ be the projection onto $K$, that is, $$\pi_K(x)=\mathrm{argmin}_{k\in\mathbb{R}^n}\{\|x-k\|_2:k\in K\}.$$ Let $\|\cdot\|_2$ denote the Euclidean $2$-norm. I want to show that for all $x,y\in\mathbb{R}^n$, we have $$\|\pi_K(x)-\pi_K(y)\|_2\le \|x-y\|_2.$$

An article I am reading claims this is trivial, but I'm not sure how to proceed. It seems intuitively true if $K$ is a projection onto a subspace, say onto $K=\mathrm{span}(e_1,\dots,e_k)$ for some $k<n$ (since in the last few coordinates, nothing is contributing to the $2$-norm).

$\endgroup$
2
$\begingroup$

Note that since $K$ is convex from definition of the projection you have for all $k \in K$ and $\lambda \in (0 ,1)$ that $$ \| x - \pi_{K} (x) \|^2 \leq \|x -(\lambda k +(1- \lambda) \pi_{K} (x)) \|^2 = \| x - \pi_{K} (x) - \lambda (k - \pi_{K} (x)) \|^2$$ By opening up the above norm-squared and letting $\lambda \to 0$, you can conclude that $$ \langle x - \pi_{K} (x) \; , \; k - \pi_{K} (x) \rangle \leq 0 \quad \quad \forall k\in K $$ similarly $$ \langle y - \pi_{K} (y) \; , \; k - \pi_{K} (y) \rangle \leq 0 \quad \quad \forall k\in K $$

Now by settting $k = \pi_{K} (y)$ in first inequality and then $k = \pi_{K} (x)$ in the second inequality, afteradding later inequality we have $$ \langle x-y + (\pi_{K}(y) - \pi_{K} (x) ) \; , \; \pi_{K}(y) - \pi_{K} (x) \rangle \leq 0 $$ Thus $$ \| \pi_{K}(y) - \pi_{K} (x)\|^2 \leq \langle x-y \; , \; \pi_{K}(y) - \pi_{K} (x) \rangle \leq \; \| y -x \| \; \| \pi_{K}(y) - \pi_{K} (x)\| $$ This gives you the desired inequality.

$\endgroup$
  • $\begingroup$ I'm actually not able to see the first inequality: how does one easily show this? $\endgroup$ – FakeAnalyst56 Jun 24 at 19:32
  • $\begingroup$ Just wrote one more line . Is it clear now? @FakeAnalyst56 $\endgroup$ – Red shoes Jun 24 at 19:45
  • $\begingroup$ Your most recent comment clarified the issue (the one using convexity and $\lambda$) and I managed to work out the details. Thank you very much for the additional help. @Red $\endgroup$ – FakeAnalyst56 Jun 24 at 20:06
  • $\begingroup$ The sad part is that I have answered this before and should know better :-( math.stackexchange.com/a/1074244/27978. $\endgroup$ – copper.hat Jun 25 at 0:27
2
$\begingroup$

(This is a rewrite of an egregiously incorrect previous answer.)

I have always found the usual proof of this fact a little unsatisfactory and lacking in geometric intuition. Here is a more intuitive proof.

$K$ needs to be closed to ensure that a $\min$ exists.

Let $L$ be the line $p(t) = \pi_K(x)+t (\pi_K(y)-\pi_K(y))$ and let $P$ be the orthogonal projection onto this line. It is straightforward to show that $\|P\| = 1$, and hence $\|Px-Py\| \le \|x-y\|$. This is the essential fact here.

Let $t_x,t_y$ be such that $p(t_x) = Px, p(t_y) = Py$. Note that we must have $t_x \le 0$ and $t_y \ge 1$, as otherwise the definition of $\pi_K(x)$ or $\pi_K(y)$ would be contradicted. Then $\|Px-Py\| = \|p(t_x)-p(t_y)\| = (t_y-t_x) \| \pi_K(x)-\pi_K(y)\| \ge \| \pi_K(x)-\pi_K(y)\|$.

$\endgroup$
  • 1
    $\begingroup$ Well, any norm and projection $\pi_K$ that satisfies the above will give the above result, but it does not hold for an arbitrary norm. At a minimum, the minimiser must be unique. $\endgroup$ – copper.hat Jun 24 at 0:27
  • 1
    $\begingroup$ You can't take $c =x$ ! $\endgroup$ – Red shoes Jun 24 at 19:01
  • $\begingroup$ @Redshoes: Silly me. Will fix. $\endgroup$ – copper.hat Jun 24 at 19:04
  • $\begingroup$ Hmm. I can't delete my answer. $\endgroup$ – copper.hat Jun 24 at 19:05
  • $\begingroup$ I dont care :) The thing is that My intuition tells me that this claim is not true for any arbitrary norm ! At least not true with lipschitz constant 1. So any proof using only the norm of the space might be incorrect. that's made me go through your proof and find the draw back. $\endgroup$ – Red shoes Jun 24 at 19:13

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.