15

Suppose $(M, d)$ is some $\ell_p$ metric space (not necessarily Euclidean), and $C \subseteq M$ is a closed convex set. Consider the projection function $f_C:M\rightarrow C$ defined such that: $$f_C(x) \in \arg\min_{y \in C} d(x,y)$$

Is it the case that for all $x,y \in M$: $$d(f_c(x),f_c(y)) \leq d(x,y)$$ i.e., is it the case that projections onto convex sets can never increase the distance between a pair of points?

Thomas
  • 153
  • $f_C (x)$ is not well defined in the general case. So it is necessary to use a different definition... – Tomás Jan 19 '13 at 15:47
  • Hm. What is wrong with the definition? Lets say that if $\arg\min_{y\in C}d(x,y)$ is a set with multiple elements, then $f_C(x)$ equals one (arbitrarily but uniquely) chosen element from the set. I'm not sure whether this can ever happen when $C$ is convex, however. – Thomas Jan 19 '13 at 15:54
  • THe problem is: Maybe what you want work for this element but does not work for another element. – Tomás Jan 19 '13 at 15:56
  • Can you elaborate? I don't know what you mean. – Thomas Jan 19 '13 at 16:00
  • My question is: How to choose an element from $f_C (x)$? Because you need some rule to do this and what happens if you change this rule? You have to precise these things. – Tomás Jan 19 '13 at 16:03
  • You may interpret my question as being about a family of functions $f_C(x)$, one for every choice of the tie-breaking rule. My question is whether every function in this class has the property of never expanding distances. – Thomas Jan 19 '13 at 16:06

2 Answers2

23

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'\|$.

  • 1
    Thanks, thats a great answer. Is there an easy proof that the contractive property of nearest-point projections holds in Hilbert spaces? – Thomas Jan 19 '13 at 18:03
  • 2
    Really nice proof! I've spent hours trying to construct a proof for this using pictures and the parrallelogram law, but your method really uses all the geometry beautifully! – Aerinmund Fagelson Jan 27 '16 at 10:40
0

In negative curvature this is true.

In Bridson, Haefliger, Metric Spaces of Non-positive Curvature, Prop. 2.4 there is a partial answer.

If X is a $\operatorname{CAT}(0)$ space (e.g. $\ell_p$ with the euclidean metric), and $\pi$ is a well-defined projection to a convex, geodesic subspace, then $\pi$ is non-expanding, i.e. the distances are (non-strictly) decreasing.

Dinisaur
  • 1,055