Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.