Do projections onto convex sets always decrease distances?

Solution 1:

No, the contractive property of the nearest-point projection is a special property of Hilbert spaces. Here is a counterexample in the $3$-dimensional real space with norm $\|x\|_4=(x_1^4+x_2^4+x_3^4)^{1/4}$. This is a nice norm: uniformly convex and uniformly smooth. The nearest-point projection onto any convex closed set is uniquely defined.

Consider the nearest-point projection $P$ onto the line $L=\{(t,t,t): t\in \mathbb R\}$. A point $x$ projects into $(0,0,0)$ if and only if the $t$-derivative of $(x_1-t)^4+(x_2-t)^4+(x_3-t)^4$ vanishes at $t=0$. Therefore, the preimage of $(0,0,0)$ under $P$ is the surface $S_0=\{x:x_1^3+x_2^3+x_3^3=0\}$. Since the distance is translation-invariant, $P$ commutes with translations along $L$. It follows that the preimage of $(1,1,1)$ is the surface $S_1=\{x:(x_1-1)^3+(x_2-1)^3+(x_3-1)^3=0\}$.

It remains to pick a pair of points on these two surfaces such that the distance between them is less than $\|(1,1,1)\|_4=3^{1/4}$. For example, I took $a=(2^{1/3}+1,0,0)\in S_1$ and considered the distance from $a$ to the points $(2^{1/3}s,-s,-s)\in S_0$. The minimum is attained around $s\approx 0.93$, and it is less than $2.9^{1/4}$.

Answering a follow-up question, I add a proof of the contractive property in Hilbert spaces. Let $P$ be projection onto a closed convex set $C$, and consider $a'=P(a)$ and $b'=P(b)$. Since the segment $a'b'$ is contained in $C$, we have $\|(1-t)a'+tb'-a\|\ge \|a'-a\|$ for $t\in [0,1]$. Therefore, $$0\le \frac{d}{dt}\|(1-t)a'+tb'-a\|^2\bigg|_{t=0} = 2 \langle b'-a' , a'-a \rangle \tag{1}$$ Similarly, $$\langle a'-b' , b'-b \rangle \ge 0\tag{2}$$ Now consider the function $$ d(t)=\|(1-t)a'+ta - ((1-t)b'+tb)\|^2 = \|(a'-b') + t (a-a'-b+b') \|^2 $$ which is a quadratic polynomial with nonnegative coefficient of $t^2$. From (1) and (2) we have
$$ d\,'(0) = 2 \langle a'-b' , a-a'-b+b' \rangle \ge 0 $$ Therefore $d$ is increasing on $[0,\infty)$. In particular, $d(1)\ge d(0)$ which means $\|a-b\|\ge \|a'-b'\|$.