3
$\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

4

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
    @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