Harman Patil (Editor)

Hilbert projection theorem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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, (yn) a sequence in C such that the distance squared between x and yn is below or equal to δ2 + 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 yn and ym 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 (yn) 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 y1 and y2 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