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?

  • $\begingroup$ $f_C (x)$ is not well defined in the general case. So it is necessary to use a different definition... $\endgroup$ – Tomás Jan 19 '13 at 15:47
  • $\begingroup$ 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. $\endgroup$ – Thomas Jan 19 '13 at 15:54
  • $\begingroup$ THe problem is: Maybe what you want work for this element but does not work for another element. $\endgroup$ – Tomás Jan 19 '13 at 15:56
  • $\begingroup$ Can you elaborate? I don't know what you mean. $\endgroup$ – Thomas Jan 19 '13 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Tomás Jan 19 '13 at 16:03

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
    $\begingroup$ Thanks, thats a great answer. Is there an easy proof that the contractive property of nearest-point projections holds in Hilbert spaces? $\endgroup$ – Thomas Jan 19 '13 at 18:03
  • 2
    $\begingroup$ 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! $\endgroup$ – Aerinmund Fagelson Jan 27 '16 at 10:40

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.


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.