Is the following statement true? If so, how would I prove it? If not, what is a counterexample?
For any convex set $S\subset \mathbb R^n$, for any point $x\in \mathbb R^n$ and $y\in S$,
$$\|\text{proj}_S(x) - y\|_2 \leq \|x-y\|_2$$
where $\text{proj}_S(x)$ is the Euclidean projection of $x$ on $S$
$$\text{proj}_S(x) = \arg\min_{u\in S}\|x-u\|_2^2$$
(For context, I am trying to proofread someone else's proof (not hmwk).)
So far, I have
- been unable to drawn a single picture in which a counterexample holds
- am playing around with the following three properties, with $x_s = \text{proj}_S(x)$:
1) $(x-x_s)^T(y-x_s) \leq 0$ (normal cone / optimality condition)
2) $\|x-x_s\|\leq\|x-y\|$ (distance to projection always closest)
3) $\|x-x_s\|^2 + \|x-y\|^2 \geq |(x-x_s)^T(y-x_s)|$ (completing the square)
I feel like I'm close!
Ok, this might have been much easier than I thought. Assume the contradiction:
$$\|x_s-y\| > \|x-y\|.$$
Then expanding out, we have
$$A: x_s^Tx_s - 2x_s^Ty > x^Tx-2x^Ty$$
Now let's insert the normal cone constraint
$$B: (x−x_s)^T(y−x_s)= x_s^Tx_s - x_s^T(y+x) + x^Ty\leq 0$$
add $A + 2\times B$ and simplify
$$x_s^Tx_s + x^Tx - 2x_s^Tx = \|x_s-x\|^2_2 < 0$$
which of course is a contradiction.
In other words, the normal cone constraint alone is equivalent to the original statement.