Hilbert projection theorem - Alchetron, the free social encyclopedia

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 ⊂ H , there exists a unique point y ∈ C for which ∥ x − y ∥ 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 ⟨ y n − x , y m − x ⟩

and

4 ∥ y n + y m 2 − x ∥ 2 = ∥ y n − x ∥ 2 + ∥ y m − x ∥ 2 + 2 ⟨ y n − x , y m − x ⟩

We have therefore:

∥ y n − y m ∥ 2 = 2 ∥ y n − x ∥ 2 + 2 ∥ y m − x ∥ 2 − 4 ∥ y n + y m 2 − x ∥ 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 ≤ 2 ( δ 2 + 1 n ) + 2 ( δ 2 + 1 m ) − 4 δ 2 = 2 ( 1 n + 1 m )

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 ∥ y 1 + y 2 2 − x ∥ 2

Since y 1 + y 2 2 belongs to C, we have ∥ y 1 + y 2 2 − x ∥ 2 ≥ δ 2 and therefore

∥ y 2 − y 1 ∥ 2 ≤ 2 δ 2 + 2 δ 2 − 4 δ 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 ∈ M such that ⟨ z − x , a ⟩ = 0 for all a ∈ M . ∥ x − a ∥ 2 = ∥ z − x ∥ 2 + ∥ a − z ∥ 2 + 2 ⟨ z − x , a − z ⟩ = ∥ z − x ∥ 2 + ∥ a − z ∥ 2 which proves that z is a minimizer.

The condition is necessary: Let y ∈ M be the minimizer. Let a ∈ M and t ∈ R .

∥ ( y + t a ) − x ∥ 2 − ∥ y − x ∥ 2 = 2 t ⟨ y − x , a ⟩ + t 2 ∥ a ∥ 2 = 2 t ⟨ y − x , a ⟩ + O ( t 2 )

is always non-negative. Therefore, ⟨ y − x , a ⟩ = 0.

QED

References

Hilbert projection theorem Wikipedia

(Text) CC BY-SA