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.

Let $C$ be a closed convex subset of a Hilbert space $H$, let $\omega \in C$, $\tau \notin C$. According to the Hilbert projection theorem, there is a unique point $\tau' \in C$ such that $\Vert \tau - \tau' \Vert = \min_{\sigma \in C} \Vert \tau - \sigma \Vert$.

Drawing a picture, it seems obvious to me that $\Vert \omega - \tau' \Vert \leq \Vert \omega - \tau \Vert$. However, I don't know how to prove it. Can anyone help me?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I have skipped some details below for brevity.

First, notice that $C$ is contained in a half-space that separates the set from $\tau$, specifically $\langle w-\tau,\tau'-\tau \rangle \geq ||\tau-\tau'||^2$. This is the first order optimality condition for the distance minimization problem. (To see this, note that $|| (\lambda w + (1-\lambda) \tau')-\tau||^2 - ||\tau'-\tau||^2 \geq 0$, $\forall \lambda \in [0,1]$, by convexity. Now expand the expression, divide across by $\lambda>0$ and then let $\lambda \rightarrow 0$. )

Then form the following estimate: $|| w - \tau||^2 = ||w - \tau' + \tau' - \tau||^2 = || w - \tau'||^2 + 2 \langle w-\tau',\tau'-\tau \rangle + ||\tau' - \tau||^2$ $= || w - \tau'||^2 + 2 (\langle w-\tau,\tau'-\tau \rangle -||\tau' - \tau||^2)+ ||\tau' - \tau||^2$ $\geq || w - \tau'||^2 + ||\tau' - \tau||^2$. This is slightly stronger than the result you were looking for.

share|improve this answer
    
There seems to be some mistake in the last inequalities. –  Ashok Apr 9 '12 at 7:17
    
Thanks @Ashok, I removed the errant '. –  copper.hat Apr 9 '12 at 8:11
    
Perfect, thanks a lot! –  Tom Jonathan Apr 9 '12 at 8:22
    
@copper.hat, I am wondering, in $\mathbb{R}^n$, whether the result you have proved holds only for $\ell_2$-norm (i.e., only in Hilbert spaces). –  Ashok Apr 9 '12 at 14:36
    
I don't know about only in Hilbert space. If you choose the $l_{\infty}$ norm it is not true. Take $C = \{ (x_1,x_2) | x_2 \geq 1 \} $, and $\tau = 0$. Choose $\tau' = (1,1)$, it is easy to see this minimizes the $l_{\infty}$ norm. Now choose $w = (-1,1)$. Then $||w-\tau'|| = 2$, whereas $||w-\tau|| = 1$, which violates the desired inequality. –  copper.hat Apr 9 '12 at 17:06
show 7 more comments

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.