Hilbert projection theorem

In mathematics, the Hilbert projection theorem is a famous result of convex analysis that says that for every point $x$ in a Hilbert space $H$ and every nonempty closed convex $C \subset H$ , there exists a unique point $y \in C$ for which $\lVert x - y \rVert$ is minimized over $C$ .

This is, in particular, true for any closed subspace $M$ of $C$ . In that case, a necessary and sufficient condition for $y$ is that the vector $x-y$ be orthogonal to $M$ .

Proof

Let us show the existence of y:

Let δ be the distance between x and C, (y_n) a sequence in C such that the distance squared between x and y_n is below or equal to δ² + 1/n. Let n and m be two integers, then the following equalities are true:

\| y_n - y_m \|^2 = \|y_n -x\|^2 + \|y_m -x\|^2 - 2 \langle y_n - x \, , \, y_m - x\rangle

and

4 \left\| \frac{y_n + y_m}2 -x \right\|^2 = \|y_n -x\|^2 + \|y_m -x\|^2 + 2 \langle y_n - x \, , \, y_m - x\rangle

We have therefore:

\| y_n - y_m \|^2 = 2\|y_n -x\|^2 + 2\|y_m -x\|^2 - 4\left\| \frac{y_n + y_m}2 -x \right\|^2

By giving an upper bound to the first two terms of the equality and by noticing that the middle of y_n and y_m belong to C and has therefore a distance greater than or equal to δ from x, one gets :

\| y_n - y_m \|^2 \; \le \; 2\left(\delta^2 + \frac 1n\right) + 2\left(\delta^2 + \frac 1m\right) - 4\delta^2=2\left( \frac 1n + \frac 1m\right)

The last inequality proves that (y_n) is a Cauchy sequence. Since C is complete, the sequence is therefore convergent to a point y in C, whose distance from x is minimal.

Let us show the uniqueness of y :

Let y₁ and y₂ be two minimizers. Then:

\| y_2 - y_1 \|^2 = 2\|y_1 -x\|^2 + 2\|y_2 -x\|^2 - 4\left\| \frac{y_1 + y_2}2 -x \right\|^2

Since $\frac{y_1 + y_2}2$ belongs to C, we have $\left\| \frac{y_1 + y_2}2 -x \right\|^2\geq \delta^2$ and therefore

\| y_2 - y_1 \|^2 \leq 2\delta^2 + 2\delta^2 - 4\delta^2=0 \,

Hence $y_1=y_2$ , which proves uniqueness.

Let us show the equivalent condition on y when C = M is a closed subspace.

The condition is sufficient: Let $z\in M$ such that $\langle z-x, a \rangle=0$ for all $a\in M$ . $\|x-a\|^2=\|z-x\|^2+\|a-z\|^2+2\langle z-x, a-z \rangle=\|z-x\|^2+\|a-z\|^2$ which proves that $z$ is a minimizer.