Jump to content

Hilbert projection theorem

From Wikipedia, the free encyclopedia

In mathematics, the Hilbert projection theorem is a famous result of convex analysis that says that for every vector x in a Hilbert space H and every nonempty closed convex C⊆H, there exists a unique vector m∈C for which ‖c−x‖ is minimized over the vectors c∈C; that is, such that ‖m−x‖≤‖c−x‖ for every c∈C.

Finite dimensional case

[edit]

Some intuition for the theorem can be obtained by considering the first order condition of the optimization problem.

Consider a finite dimensional real Hilbert space H with a subspace C and a point x. If m∈C is a minimizer or minimum point of the function N:C→ℝ defined by N(c):=‖c−x‖ (which is the same as the minimum point of c↦‖c−x‖2), then derivative must be zero at m.

In matrix derivative notation:[1] ∂‖x−c‖2=∂⟨c−x,c−x⟩=2⟨c−x,∂c⟩ Since ∂c is a vector in C that represents an arbitrary tangent direction, it follows that m−x must be orthogonal to every vector in C.

Statement

[edit]

Hilbert projection theorem—For every vector x in a Hilbert space H and every nonempty closed convex C⊆H, there exists a unique vector m∈C for which ‖x−m‖ is equal to δ:=infc∈C‖x−c‖.

If the closed subset C is also a vector subspace of H then this minimizer m is the unique element in C such that x−m is orthogonal to C.

Detailed elementary proof

[edit]
Proof that a minimum point y exists

Let δ:=infc∈C‖x−c‖ be the distance between x and C, (cn)n=1∞ a sequence in C such that the distance squared between x and cn is less than or equal to δ2+1/n. Let n and m be two integers, then the following equalities are true: ‖cn−cm‖2=‖cn−x‖2+‖cm−x‖2−2⟨cn−x,cm−x⟩ and 4‖cn+cm2−x‖2=‖cn−x‖2+‖cm−x‖2+2⟨cn−x,cm−x⟩ Therefore ‖cn−cm‖2=2‖cn−x‖2+2‖cm−x‖2−4‖cn+cm2−x‖2 (This equation is the same as the formula a2=2b2+2c2−4Ma2 for the length Ma of a median in a triangle with sides of length a,b, and c, where specifically, the triangle's vertices are x,cm,cn).

By giving an upper bound to the first two terms of the equality and by noticing that the midpoint of cn and cm belong to C and has therefore a distance greater than or equal to δ from x, it follows that: ‖cn−cm‖2≤2(δ2+1n)+2(δ2+1m)−4δ2=2(1n+1m)

The last inequality proves that (cn)n=1∞ is a Cauchy sequence. Since C is complete, the sequence is therefore convergent to a point m∈C, whose distance from x is minimal. ◼

Proof that m is unique

Let m1 and m2 be two minimum points. Then: ‖m2−m1‖2=2‖m1−x‖2+2‖m2−x‖2−4‖m1+m22−x‖2

Since m1+m22 belongs to C, we have ‖m1+m22−x‖2≥δ2 and therefore ‖m2−m1‖2≤2δ2+2δ2−4δ2=0.

Hence m1=m2, which proves uniqueness. ◼

Proof of characterization of minimum point when C is a closed vector subspace

Assume that C is a closed vector subspace of H. It must be shown the minimizer m is the unique element in C such that ⟨m−x,c⟩=0 for every c∈C.

Proof that the condition is sufficient: Let z∈C be such that ⟨z−x,c⟩=0 for all c∈C. If c∈C then c−z∈C and so ‖c−x‖2=‖(z−x)+(c−z)‖2=‖z−x‖2+‖c−z‖2+2⟨z−x,c−z⟩=‖z−x‖2+‖c−z‖2 which implies that ‖z−x‖2≤‖c−x‖2. Because c∈C was arbitrary, this proves that ‖z−x‖=infc∈C‖c−x‖ and so z is a minimum point.

Proof that the condition is necessary: Let m∈C be the minimum point. Let c∈C and t∈ℝ. Because m+tc∈C, the minimality of m guarantees that ‖m−x‖≤‖(m+tc)−x‖. Thus ‖(m+tc)−x‖2−‖m−x‖2=2t⟨m−x,c⟩+t2‖c‖2 is always non-negative and ⟨m−x,c⟩ must be a real number. If ⟨m−x,c⟩≠0 then the map f(t):=2t⟨m−x,c⟩+t2‖c‖2 has a minimum at t0:=−⟨m−x,c⟩‖c‖2 and moreover, f(t0)<0, which is a contradiction. Thus ⟨m−x,c⟩=0. ◼

Proof by reduction to a special case

[edit]

It suffices to prove the theorem in the case of x=0 because the general case follows from the statement below by replacing C with C−x.

Hilbert projection theorem (case x=0)[2]—For every nonempty closed convex subset C⊆H of a Hilbert space H, there exists a unique vector m∈C such that infc∈C‖c‖=‖m‖.

Furthermore, letting d:=infc∈C‖c‖, if (cn)n=1∞ is any sequence in C such that limn→∞‖cn‖=d in ℝ[note 1] then limn→∞cn=m in H.

Proof

Let C be as described in this theorem and let d:=infc∈C‖c‖. This theorem will follow from the following lemmas.

Lemma 1—If c∙:=(cn)n=1∞ is any sequence in C such that limn→∞‖cn‖=d in ℝ then there exists some c∈C such that limn→∞cn=c in H. Furthermore, ‖c‖=d.

Lemma 2—A sequence (cn)n=1∞ satisfying the hypotheses of Lemma 1 exists.

Lemma 2 and Lemma 1 together prove that there exists some c∈C such that ‖c‖=d. Lemma 1 can be used to prove uniqueness as follows. Suppose b∈C is such that ‖b‖=d and denote the sequence b,c,b,c,b,c,… by (cn)n=1∞ so that the subsequence (c2n)n=1∞ of even indices is the constant sequence c,c,c,… while the subsequence (c2n−1)n=1∞ of odd indices is the constant sequence b,b,b,…. Because ‖cn‖=d for every n∈ℕ, limn→∞‖cn‖=limn→∞d=d in ℝ, which shows that the sequence (cn)n=1∞ satisfies the hypotheses of Lemma 1. Lemma 1 guarantees the existence of some x∈C such that limn→∞cn=x in H. Because (cn)n=1∞ converges to x, so do all of its subsequences. In particular, the subsequence c,c,c,… converges to x, which implies that x=c (because limits in H are unique and this constant subsequence also converges to c). Similarly, x=b because the subsequence b,b,b,… converges to both x and b. Thus b=c, which proves the theorem. ◼

Consequences

[edit]

Proposition—If C is a closed vector subspace of a Hilbert space H then[note 3] H=C⊕C⊥.

Properties

[edit]

Expression as a global minimum

The statement and conclusion of the Hilbert projection theorem can be expressed in terms of global minimums of the following functions. Their notation will also be used to simplify certain statements.

Given a non-empty subset C⊆H and some x∈H, define a function dC,x:C→[0,∞) by c↦‖x−c‖. A global minimum point of dC,x, if one exists, is any point m in domain⁡dC,x=C such that dC,x(m)≤dC,x(c) for all c∈C, in which case dC,x(m)=‖m−x‖ is equal to the global minimum value of the function dC,x, which is: infc∈CdC,x(c)=infc∈C‖x−c‖.

Effects of translations and scalings

When this global minimum point m exists and is unique then denote it by min⁡(C,x); explicitly, the defining properties of min⁡(C,x) (if it exists) are: min⁡(C,x)∈C and ‖x−min⁡(C,x)‖≤‖x−c‖ for all c∈C. The Hilbert projection theorem guarantees that this unique minimum point exists whenever C is a non-empty closed and convex subset of a Hilbert space. However, such a minimum point can also exist in non-convex or non-closed subsets as well; for instance, just as long is C is non-empty, if x∈C then min⁡(C,x)=x.

If C⊆H is a non-empty subset, s is any scalar, and x,x0∈H are any vectors then min⁡(sC+x0,sx+x0)=smin⁡(C,x)+x0 which implies: min(sC,sx)=smin⁡(C,x)min(−C,−x)=−min⁡(C,x) min⁡(C+x0,x+x0)=min⁡(C,x)+x0min⁡(C−x0,x−x0)=min⁡(C,x)−x0 min(C,−x)=min⁡(C+x,0)−xmin(C,0)+x=min⁡(C+x,x)min(C−x,0)=min⁡(C,x)−x

Examples

The following counter-example demonstrates a continuous linear isomorphism A:H→H for which min⁡(A(C),A(x))≠A(min⁡(C,x)). Endow H:=ℝ2 with the dot product, let x0:=(0,1), and for every real s∈ℝ, let Ls:={(x,sx):x∈ℝ} be the line of slope s through the origin, where it is readily verified that min⁡(Ls,x0)=s1+s2(1,s). Pick a real number r≠0 and define A:ℝ2→ℝ2 by A(x,y):=(rx,y) (so this map scales the x−coordinate by r while leaving the y−coordinate unchanged). Then A:ℝ2→ℝ2 is an invertible continuous linear operator that satisfies A(Ls)=Ls/r and A(x0)=x0, so that min⁡(A(Ls),A(x0))=sr2+s2(1,s) and A(min⁡(Ls,x0))=s1+s2(r,s). Consequently, if C:=Ls with s≠0 and if (r,s)≠(±1,1) then min⁡(A(C),A(x0))≠A(min⁡(C,x0)).

Iterated projections

[edit]

For any closed convex nonempty subset C⊂H, let PC:H→C be the projection function.

If there are multiple closed convex subsets C1,C2,…,Cn, then one can approximate the projection operator PC1∩⋯∩Cn by applying PC1,PC2,…,PCn in sequence, then do it again and again. That is, one can approximate (PCn…PC2PC1)k→PC1∩⋯∩Cn as k→∞. The Kaczmarz method is a commonly used special case. Such methods can be computationally effective. For example, if C is a complicated shape, then projecting directly to C may be difficult. However, C can be approximated as an intersection of simple objects like half-spaces, hyperplanes, finite-dimensional subspaces, or cones.[4]

If C is a closed subspace, then it is convex. In this case, the projection function P:H→C is an orthogonal projection (a continuous linear operator that is self-adjoint). A classic theorem states that, if C1,…,Cn are closed subspaces, then[5] limk→∞‖(PC1⋯PCn)kx−PC1∩⋯∩Cnx‖=0,∀x∈H

See also

[edit]

Notes

[edit]
  1. ↑ Because the norm ‖⋅‖:H→ℝ is continuous, if limn→∞xn converges in H then necessarily limn→∞‖xn‖ converges in ℝ. But in general, the converse is not guaranteed. However, under this theorem's hypotheses, knowing that limn→∞‖cn‖=d in ℝ is sufficient to conclude that limn→∞cn converges in H.
  2. ↑ Explicitly, this means that given any ϵ>0 there exists some integer N>0 such that "the quantity" is ≤ϵ whenever m,n≥N. Here, "the quantity" refers to the inequality's right hand side 2‖cm‖2+2‖cn‖2−4d2 and later in the proof, "the quantity" will also refer to ‖cm−cn‖2 and then ‖cm−cn‖. By definition of "Cauchy sequence," (cn)n=1∞ is Cauchy in H if and only if "the quantity" ‖cm−cn‖ satisfies this aforementioned condition.
  3. ↑ Technically, H=K⊕K⊥ means that the addition map K×K⊥→H defined by (k,p)↦k+p is a surjective linear isomorphism and homeomorphism. See the article on complemented subspaces for more details.

References

[edit]
  1. ↑ Petersen, Kaare. "The Matrix Cookbook" (PDF). Retrieved 9 January 2021.
  2. ↑ Rudin 1991, pp. 306–309.
  3. ↑ Rudin 1991, pp. 307−309.
  4. ↑ Deutsch, Frank (2001), "The Method of Alternating Projections", Best Approximation in Inner Product Spaces, New York, NY: Springer New York, pp. 193–235, doi:10.1007/978-1-4684-9298-9_9, ISBN 978-1-4419-2890-0
  5. ↑ Netyanun, Anupan; Solmon, Donald C. (August 2006). "Iterated Products of Projections in Hilbert Space". The American Mathematical Monthly. 113 (7): 644–648. doi:10.1080/00029890.2006.11920347. ISSN 0002-9890.

Bibliography

[edit]