2
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    There seems to be some mistake in the last inequalities.2012-04-09
  • 0
    Thanks @Ashok, I removed the errant '.2012-04-09
  • 0
    Perfect, thanks a lot!2012-04-09
  • 0
    @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).2012-04-09
  • 0
    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.2012-04-09
  • 0
    @Ashok: I suspect, 'though I haven't attempted to show it, that the result would hold in strictly convex Banach spaces.2012-04-10
  • 0
    I think it might depend on how one generalizes the question to the case of normed spaces, where there is no unique norm-distance minimizer, in general. If one requires $\Vert \omega - \tau'\Vert \leq \Vert \omega - \tau \Vert$ for every minimizer, then the statement is false, as your example shows. But what if one only requires the existence of a norm-distance minimizer $\tau'$ such that $\Vert \omega - \tau'\Vert \leq \Vert \omega - \tau \Vert$? In your example, one might choose $\tau' = (-1, 1)$ as a minimizer satisfying $\Vert \omega - \tau'\Vert \leq \Vert \omega - \tau \Vert$.2012-04-10
  • 0
    Did you mean $\tau' = (0,1)$?2012-04-10
  • 0
    Euh, do I make a mistake here? I think that $\tau' = (-1,1)$ is a valid example for a minimizer, right? I really mean $\tau' = (-1,1)$. Well, $\tau' = (0,1)$ would be another valid example with $\Vert \omega - \tau' \Vert \leq \Vert \omega - \tau \Vert$, yes.2012-04-10
  • 0
    The set of minimizers is $[-1,1] \times \{1\}$, so yes, $(-1,1)$ is a valid minimizer. But it violates your requirement that $||w-\tau'|| \leq ||w - \tau||$ $\forall w \in C$. The only point in this example which satisfies this condition is $(0,1)$.2012-04-10
  • 0
    Ah, I see. In your case, the inequality is ment to be satisfied for all $\omega \in C$. I only wanted the inequality to be satisfied for a given $\omega$, in this case for $\omega = (-1, 1)$.2012-04-10
  • 0
    @copper.hat: I am rather interested in your stronger result $||w - \tau||^2\geq || w - \tau'||^2 + ||\tau' - \tau||^2$ for all $w\in C$. I know that its not true for $\ell_p$ distances $p>1, p\neq 2$ as you can see from [this](http://math.stackexchange.com/questions/107037/pythagoras-theorem-for-l-p-spaces). But I don't know how to prove that its only true for $\ell_2$ distance.2012-04-10