Английская Википедия:Hilbert projection theorem
Шаблон:Short description Шаблон:One source In mathematics, the Hilbert projection theorem is a famous result of convex analysis that says that for every vector <math>x</math> in a Hilbert space <math>H</math> and every nonempty closed convex <math>C \subseteq H,</math> there exists a unique vector <math>m \in C</math> for which <math>\|c - x\|</math> is minimized over the vectors <math>c \in C</math>; that is, such that <math>\|m - x\| \leq \|c - x\|</math> for every <math>c \in C.</math>
Finite dimensional case
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 <math>H</math> with a subspace <math>C</math> and a point <math>x.</math> If <math>m \in C</math> is a Шаблон:Em or Шаблон:Em of the function <math>N : C \to \R</math> defined by <math>N(c) := \|c - x\|</math> (which is the same as the minimum point of <math>c \mapsto \|c - x\|^2</math>), then derivative must be zero at <math>m.</math>
In matrix derivative notation[1] <math display=block>\begin{aligned} \partial \lVert x - c \rVert^2 &= \partial \langle c - x, c - x \rangle \\ &= 2 \langle c - x, \partial c\rangle \end{aligned}</math> Since <math>\partial c</math> is a vector in <math>C</math> that represents an arbitrary tangent direction, it follows that <math>m - x</math> must be orthogonal to every vector in <math>C.</math>
Statement
Detailed elementary proof
Proof by reduction to a special case
It suffices to prove the theorem in the case of <math>x = 0</math> because the general case follows from the statement below by replacing <math>C</math> with <math>C - x.</math>
Consequences
Шаблон:Collapse top Шаблон:Em:
If <math>c \in C \cap C^{\bot}</math> then <math>0 = \langle \,c, \,c\, \rangle = \|c\|^2,</math> which implies <math>c = 0.</math> <math>\blacksquare</math>
Let <math>P := \prod_{c \in C} \mathbb{F}</math> where <math>\mathbb{F}</math> is the underlying scalar field of <math>H</math> and define <math display=block>\begin{alignat}{4} L : \,& H && \to \,&& P \\
& h && \mapsto\,&& \left(\langle \,h, \,c\, \rangle\right)_{c \in C} \\
\end{alignat}</math> which is continuous and linear because this is true of each of its coordinates <math>h \mapsto \langle h, c \rangle.</math> The set <math>C^{\bot} = L^{-1}(0) = L^{-1}\left(\{ 0 \}\right)</math> is closed in <math>H</math> because <math>\{ 0 \}</math> is closed in <math>P</math> and <math>L : H \to P</math> is continuous. The kernel of any linear map is a vector subspace of its domain, which is why <math>C^{\bot} = \ker L</math> is a vector subspace of <math>H.</math> <math>\blacksquare</math>
Let <math>x \in H.</math> The Hilbert projection theorem guarantees the existence of a unique <math>m \in C</math> such that <math>\|x - m\| \leq \|x - c\| \text{ for all } c \in C</math> (or equivalently, for all <math>x - c \in x - C</math>). Let <math>p := x - m</math> so that <math>x = m + p \in C + p</math> and it remains to show that <math>p \in C^{\bot}.</math> The inequality above can be rewritten as: <math display=block>\|p\| \leq \|z\| \quad \text{ for all } z \in x - C.</math> Because <math>m \in C</math> and <math>C</math> is a vector space, <math>m + C = C</math> and <math>C = - C,</math> which implies that <math>x - C = x + C = p + m + C = p + C.</math> The previous inequality thus becomes <math display=block>\|p\| \leq \|z\| \quad \text{ for all } z \in p + C.</math> or equivalently, <math display=block>\|p\| \leq \|p + c\| \quad \text{ for all } c \in C.</math> But this last statement is true if and only if <math>\langle \,p, c\, \rangle = 0</math> every <math>c \in C.</math> Thus <math>p \in C^{\bot}.</math> <math>\blacksquare</math> Шаблон:Collapse bottom
Properties
Expression as a global minimum
The statement and conclusion of the Hilbert projection theorem can be expressed in terms of global minimums of the followings functions. Their notation will also be used to simplify certain statements.
Given a non-empty subset <math>C \subseteq H</math> and some <math>x \in H,</math> define a function <math display=block>d_{C,x} : C \to [0, \infty) \quad \text{ by } c \mapsto \|x - c\|.</math> A Шаблон:Em of <math>d_{C,x},</math> if one exists, is any point <math>m</math> in <math>\,\operatorname{domain} d_{C,x} = C\,</math> such that <math display=block>d_{C,x}(m) \,\leq\, d_{C,x}(c) \quad \text{ for all } c \in C,</math> in which case <math>d_{C,x}(m) = \|m - x\|</math> is equal to the Шаблон:Em of the function <math>d_{C, x},</math> which is: <math display=block>\inf_{c \in C} d_{C,x}(c) = \inf_{c \in C} \|x - c\|.</math>
Effects of translations and scalings
When this global minimum point <math>m</math> exists and is unique then denote it by <math>\min(C, x);</math> explicitly, the defining properties of <math>\min(C, x)</math> (if it exists) are: <math display=block>\min(C, x) \in C \quad \text { and } \quad \left\|x - \min(C, x)\right\| \leq \|x - c\| \quad \text{ for all } c \in C.</math> The Hilbert projection theorem guarantees that this unique minimum point exists whenever <math>C</math> 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 <math>C</math> is non-empty, if <math>x \in C</math> then <math>\min(C, x) = x.</math>
If <math>C \subseteq H</math> is a non-empty subset, <math>s</math> is any scalar, and <math>x, x_0 \in H</math> are any vectors then <math display=block>\,\min\left(s C + x_0, s x + x_0\right) = s \min(C, x) + x_0</math> which implies: <math display=block>\begin{alignat}{6} \min&(s C, s x) &&= s &&\min(C, x) \\ \min&(- C, - x) &&= - &&\min(C, x) \\ \end{alignat}</math> <math display=block>\begin{alignat}{6} \min\left(C + x_0, x + x_0\right) &= \min(C, x) + x_0 \\ \min\left(C - x_0, x - x_0\right) &= \min(C, x) - x_0 \\ \end{alignat}</math> <math display=block>\begin{alignat}{6} \min&(C, - x) {} &&= \min(C + x, 0) - x \\ \min&(C, 0) \;+\; x\;\;\;\; &&= \min(C + x, x) \\ \min&(C - x, 0) {} &&= \min(C, x) - x \\ \end{alignat}</math>
Examples
The following counter-example demonstrates a continuous linear isomorphism <math>A : H \to H</math> for which <math>\,\min(A(C), A(x)) \neq A(\min(C, x)).</math> Endow <math>H := \R^2</math> with the dot product, let <math>x_0 := (0, 1),</math> and for every real <math>s \in \R,</math> let <math>L_s := \{ (x, s x) : x \in \R \}</math> be the line of slope <math>s</math> through the origin, where it is readily verified that <math>\min\left(L_s, x_0\right) = \frac{s}{1+s^2}(1, s).</math> Pick a real number <math>r \neq 0</math> and define <math>A : \R^2 \to \R^2</math> by <math>A(x, y) := (r x, y)</math> (so this map scales the <math>x-</math>coordinate by <math>r</math> while leaving the <math>y-</math>coordinate unchanged). Then <math>A : \R^2 \to \R^2</math> is an invertible continuous linear operator that satisfies <math>A\left(L_s\right) = L_{s/r}</math> and <math>A\left(x_0\right) = x_0,</math> so that <math>\,\min\left(A\left(L_s\right), A\left(x_0\right)\right) = \frac{s}{r^2 + s^2} (1, s)</math> and <math>A\left(\min\left(L_s, x_0\right)\right) = \frac{s}{1 + s^2} \left(r, s\right).</math> Consequently, if <math>C := L_s</math> with <math>s \neq 0</math> and if <math>(r, s) \neq (\pm 1, 1)</math> then <math>\,\min(A(C), A\left(x_0\right)) \neq A\left(\min\left(C, x_0\right)\right).</math>
See also
Notes
References
Bibliography
Шаблон:Functional analysis Шаблон:Hilbert space
