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 $H$ . 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}\;\leq \;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.