Hilbert projection theorem

In mathematics, the Hilbert projection theorem is a famous result of convex analysis that says that for every vector ${\displaystyle x}$ in a Hilbert space ${\displaystyle H}$ and every nonempty closed convex ${\displaystyle C\subseteq H,}$ there exists a unique vector ${\displaystyle m\in C}$ for which ${\displaystyle \|c-x\|}$ is minimized over the vectors ${\displaystyle c\in C}$; that is, such that ${\displaystyle \|m-x\|\leq \|c-x\|}$ for every ${\displaystyle c\in C.}$

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 ${\displaystyle H}$ with a subspace ${\displaystyle C}$ and a point ${\displaystyle x.}$ If ${\displaystyle m\in C}$ is a minimizer or minimum point of the function ${\displaystyle N:C\to \mathbb {R} }$ defined by ${\displaystyle N(c):=\|c-x\|}$ (which is the same as the minimum point of ${\displaystyle c\mapsto \|c-x\|^{2}}$), then derivative must be zero at ${\displaystyle m.}$

In matrix derivative notation^[1]

$${\displaystyle {\begin{aligned}\partial \lVert x-c\rVert ^{2}&=\partial \langle c-x,c-x\rangle \\&=2\langle c-x,\partial c\rangle \end{aligned}}}$$

${\displaystyle \partial c}$

${\displaystyle C}$

${\displaystyle m-x}$

${\displaystyle C.}$

Statement

Detailed elementary proof

Proof that a minimum point ${\displaystyle y}$ exists

Let ${\displaystyle \delta :=\inf _{c\in C}\|x-c\|}$ be the distance between ${\displaystyle x}$ and ${\displaystyle C,}$ ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ a sequence in ${\displaystyle C}$ such that the distance squared between ${\displaystyle x}$ and ${\displaystyle c_{n}}$ is less than or equal to ${\displaystyle \delta ^{2}+1/n.}$ Let ${\displaystyle n}$ and ${\displaystyle m}$ be two integers, then the following equalities are true:

$${\displaystyle \left\|c_{n}-c_{m}\right\|^{2}=\left\|c_{n}-x\right\|^{2}+\left\|c_{m}-x\right\|^{2}-2\left\langle c_{n}-x\,,\,c_{m}-x\right\rangle }$$

and

$${\displaystyle 4\left\|{\frac {c_{n}+c_{m}}{2}}-x\right\|^{2}=\left\|c_{n}-x\right\|^{2}+\left\|c_{m}-x\right\|^{2}+2\left\langle c_{n}-x\,,\,c_{m}-x\right\rangle }$$

Therefore

$${\displaystyle \left\|c_{n}-c_{m}\right\|^{2}=2\left\|c_{n}-x\right\|^{2}+2\left\|c_{m}-x\right\|^{2}-4\left\|{\frac {c_{n}+c_{m}}{2}}-x\right\|^{2}}$$

(This equation is the same as the formula ${\displaystyle a^{2}=2b^{2}+2c^{2}-4M_{a}^{2}}$ for the length ${\displaystyle M_{a}}$ of a median in a triangle with sides of length ${\displaystyle a,b,}$ and ${\displaystyle c,}$ where specifically, the triangle's vertices are ${\displaystyle x,c_{m},c_{n}}$).

By giving an upper bound to the first two terms of the equality and by noticing that the middle of ${\displaystyle c_{n}}$ and ${\displaystyle c_{m}}$ belong to ${\displaystyle C}$ and has therefore a distance greater than or equal to ${\displaystyle \delta }$ from ${\displaystyle x,}$ it follows that:

$${\displaystyle \|c_{n}-c_{m}\|^{2}\;\leq \;2\left(\delta ^{2}+{\frac {1}{n}}\right)+2\left(\delta ^{2}+{\frac {1}{m}}\right)-4\delta ^{2}=2\left({\frac {1}{n}}+{\frac {1}{m}}\right)}$$

The last inequality proves that ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ is a Cauchy sequence. Since ${\displaystyle C}$ is complete, the sequence is therefore convergent to a point ${\displaystyle m\in C,}$ whose distance from ${\displaystyle x}$ is minimal. ${\displaystyle \blacksquare }$

Proof that ${\displaystyle m}$ is unique

Let ${\displaystyle m_{1}}$ and ${\displaystyle m_{2}}$ be two minimum points. Then:

$${\displaystyle \|m_{2}-m_{1}\|^{2}=2\|m_{1}-x\|^{2}+2\|m_{2}-x\|^{2}-4\left\|{\frac {m_{1}+m_{2}}{2}}-x\right\|^{2}}$$

Since ${\displaystyle {\frac {m_{1}+m_{2}}{2}}}$ belongs to ${\displaystyle C,}$ we have ${\displaystyle \left\|{\frac {m_{1}+m_{2}}{2}}-x\right\|^{2}\geq \delta ^{2}}$ and therefore

$${\displaystyle \|m_{2}-m_{1}\|^{2}\leq 2\delta ^{2}+2\delta ^{2}-4\delta ^{2}=0.}$$

Hence ${\displaystyle m_{1}=m_{2},}$ which proves uniqueness. ${\displaystyle \blacksquare }$

Proof of characterization of minimum point when ${\displaystyle C}$ is a closed vector subspace

Assume that ${\displaystyle C}$ is a closed vector subspace of ${\displaystyle H.}$ It must be shown the minimizer ${\displaystyle m}$ is the unique element in ${\displaystyle C}$ such that ${\displaystyle \langle m-x,c\rangle =0}$ for every ${\displaystyle c\in C.}$

Proof that the condition is sufficient: Let ${\displaystyle z\in C}$ be such that ${\displaystyle \langle z-x,c\rangle =0}$ for all ${\displaystyle c\in C.}$ If ${\displaystyle c\in C}$ then ${\displaystyle c-z\in C}$ and so

$${\displaystyle \|c-x\|^{2}=\|(z-x)+(c-z)\|^{2}=\|z-x\|^{2}+\|c-z\|^{2}+2\langle z-x,c-z\rangle =\|z-x\|^{2}+\|c-z\|^{2}}$$

which implies that ${\displaystyle \|z-x\|^{2}\leq \|c-x\|^{2}.}$ Because ${\displaystyle c\in C}$ was arbitrary, this proves that ${\displaystyle \|z-x\|=\inf _{c\in C}\|c-x\|}$ and so ${\displaystyle z}$ is a minimum point.

Proof that the condition is necessary: Let ${\displaystyle m\in C}$ be the minimum point. Let ${\displaystyle c\in C}$ and ${\displaystyle t\in \mathbb {R} .}$ Because ${\displaystyle m+tc\in C,}$ the minimality of ${\displaystyle m}$ guarantees that ${\displaystyle \|m-x\|\leq \|(m+tc)-x\|.}$ Thus

$${\displaystyle \|(m+tc)-x\|^{2}-\|m-x\|^{2}=2t\langle m-x,c\rangle +t^{2}\|c\|^{2}}$$

is always non-negative and ${\displaystyle \langle m-x,c\rangle }$ must be a real number. If ${\displaystyle \langle m-x,c\rangle \neq 0}$ then the map ${\displaystyle f(t):=2t\langle m-x,c\rangle +t^{2}\|c\|^{2}}$ has a minimum at ${\displaystyle t_{0}:=-{\frac {\langle m-x,c\rangle }{\|c\|^{2}}}}$ and moreover, ${\displaystyle f\left(t_{0}\right)<0,}$ which is a contradiction. Thus ${\displaystyle \langle m-x,c\rangle =0.}$ ${\displaystyle \blacksquare }$

Proof by reduction to a special case

It suffices to prove the theorem in the case of ${\displaystyle x=0}$ because the general case follows from the statement below by replacing ${\displaystyle C}$ with ${\displaystyle C-x.}$

Proof

Let ${\displaystyle C}$ be as described in this theorem and let

$${\displaystyle d:=\inf _{c\in C}\|c\|.}$$

This theorem will follow from the following lemmas.

Lemma 1 — If ${\displaystyle c_{\bullet }:=\left(c_{n}\right)_{n=1}^{\infty }}$ is any sequence in ${\displaystyle C}$ such that ${\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=d}$ in ${\displaystyle \mathbb {R} }$ then there exists some ${\displaystyle c\in C}$ such that ${\displaystyle \lim _{n\to \infty }c_{n}=c}$ in ${\displaystyle H.}$ Furthermore, ${\displaystyle \|c\|=d.}$

Proof of Lemma 1

Because ${\displaystyle C}$ is convex, if ${\displaystyle m,n\in \mathbb {N} }$ then ${\displaystyle {\frac {1}{2}}\left(c_{m}+c_{n}\right)\in C}$ so that by definition of the infimum, ${\displaystyle d\leq \left\|{\frac {1}{2}}\left(c_{m}+c_{n}\right)\right\|,}$ which implies that ${\displaystyle 4d^{2}\leq \left\|c_{m}+c_{n}\right\|^{2}.}$ By the parallelogram law, $${\displaystyle \left\|c_{m}+c_{n}\right\|^{2}+\left\|c_{m}-c_{n}\right\|^{2}=2\left\|c_{m}\right\|^{2}+2\left\|c_{n}\right\|^{2}}$$ where ${\displaystyle 4d^{2}\leq \left\|c_{m}+c_{n}\right\|^{2}}$ now implies $${\displaystyle 4d^{2}+\left\|c_{m}-c_{n}\right\|^{2}~\leq ~2\left\|c_{m}\right\|^{2}+2\left\|c_{n}\right\|^{2}}$$ and so $${\displaystyle {\begin{alignedat}{4}\left\|c_{m}-c_{n}\right\|^{2}~\leq ~2\left\|c_{m}\right\|^{2}+2\left\|c_{n}\right\|^{2}-4d^{2}\end{alignedat}}}$$ The assumption ${\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=d}$ implies that the right hand side (RHS) of the above inequality can be made arbitrary close to ${\displaystyle 0}$ by making ${\displaystyle m}$ and ${\displaystyle n}$ sufficiently large.[note 2] The same must consequently also be true of the inequality's left hand side ${\displaystyle \left\|c_{m}-c_{n}\right\|^{2}}$ and thus also of ${\displaystyle \left\|c_{m}-c_{n}\right\|,}$ which proves that ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ is a Cauchy sequence in ${\displaystyle H.}$ Since ${\displaystyle H}$ is complete, there exists some ${\displaystyle c\in H}$ such that ${\displaystyle \lim _{n\to \infty }c_{n}=c}$ in ${\displaystyle H.}$ Because every ${\displaystyle c_{n}}$ belongs to ${\displaystyle C,}$ which is a closed subset of ${\displaystyle H,}$ their limit ${\displaystyle c}$ must also belongs to this closed subset, which proves that ${\displaystyle c\in C.}$ Since the norm ${\displaystyle \|\,\cdot \,\|:H\to \mathbb {R} }$ is a continuous function, ${\displaystyle \lim _{n\to \infty }c_{n}=c}$ in ${\displaystyle H}$ implies that ${\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=\|c\|}$ in ${\displaystyle \mathbb {R} .}$ But ${\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=d}$ also holds (by assumption) so that ${\displaystyle \|c\|=d}$ (because limits in ${\displaystyle \mathbb {R} }$ are unique). ${\displaystyle \blacksquare }$

Lemma 2 — A sequence ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ satisfying the hypotheses of Lemma 1 exists.

Proof of Lemma 2

The existence of the sequence follows from the definition of the infimum, as is now shown. The set ${\displaystyle S:=\{\|c\|:c\in C\}}$ is a non-empty subset of non-negative real numbers and ${\displaystyle d:=\inf _{c\in C}\|c\|=\inf S.}$ Let ${\displaystyle n\geq 1}$ be an integer. Because ${\displaystyle \inf S<d+{\frac {1}{n}},}$ there exists some ${\displaystyle s_{n}\in S}$ such that ${\displaystyle s_{n}<d+{\frac {1}{n}}.}$ Since ${\displaystyle s_{n}\in S,}$ ${\displaystyle d=\inf S\leq s_{n}}$ holds (by definition of the infimum). Thus ${\displaystyle d\leq s_{n}<d+{\frac {1}{n}}}$ and now the squeeze theorem implies that ${\displaystyle \lim _{n\to \infty }s_{n}=d}$ in ${\displaystyle \mathbb {R} .}$ (This first part of the proof works for any non-empty subset of ${\displaystyle S\subseteq \mathbb {R} }$ for which ${\displaystyle d:=\inf _{s\in S}s}$ is finite). For every ${\displaystyle n\in \mathbb {N} ,}$ the fact that ${\displaystyle s_{n}\in S=\{\|c\|:c\in C\}}$ means that there exists some ${\displaystyle c_{n}\in C}$ such that ${\displaystyle s_{n}=\left\|c_{n}\right\|.}$ The convergence ${\displaystyle \lim _{n\to \infty }s_{n}=d}$ in ${\displaystyle \mathbb {R} }$ thus becomes ${\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=d}$ in ${\displaystyle \mathbb {R} .}$ ${\displaystyle \blacksquare }$

Lemma 2 and Lemma 1 together prove that there exists some ${\displaystyle c\in C}$ such that ${\displaystyle \|c\|=d.}$ Lemma 1 can be used to prove uniqueness as follows. Suppose ${\displaystyle b\in C}$ is such that ${\displaystyle \|b\|=d}$ and denote the sequence

$${\displaystyle b,c,b,c,b,c,\ldots }$$

by ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ so that the subsequence ${\displaystyle \left(c_{2n}\right)_{n=1}^{\infty }}$ of even indices is the constant sequence ${\displaystyle c,c,c,\ldots }$ while the subsequence ${\displaystyle \left(c_{2n-1}\right)_{n=1}^{\infty }}$ of odd indices is the constant sequence ${\displaystyle b,b,b,\ldots .}$ Because ${\displaystyle \left\|c_{n}\right\|=d}$ for every ${\displaystyle n\in \mathbb {N} ,}$ ${\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=\lim _{n\to \infty }d=d}$ in ${\displaystyle \mathbb {R} ,}$ which shows that the sequence ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ satisfies the hypotheses of Lemma 1. Lemma 1 guarantees the existence of some ${\displaystyle x\in C}$ such that ${\displaystyle \lim _{n\to \infty }c_{n}=x}$ in ${\displaystyle H.}$ Because ${\displaystyle \left(c_{n}\right)_{n=1}^{\infty }}$ converges to ${\displaystyle x,}$ so do all of its subsequences. In particular, the subsequence ${\displaystyle c,c,c,\ldots }$ converges to ${\displaystyle x,}$ which implies that ${\displaystyle x=c}$ (because limits in ${\displaystyle H}$ are unique and this constant subsequence also converges to ${\displaystyle c}$). Similarly, ${\displaystyle x=b}$ because the subsequence ${\displaystyle b,b,b,\ldots }$ converges to both ${\displaystyle x}$ and ${\displaystyle b.}$ Thus ${\displaystyle b=c,}$ which proves the theorem. ${\displaystyle \blacksquare }$

Consequences

Proposition — If ${\displaystyle C}$ is a closed vector subspace of a Hilbert space ${\displaystyle H}$ then^{[note 3]}

$${\displaystyle H=C\oplus C^{\bot }.}$$

Proof[3]

Proof that ${\displaystyle C\cap C^{\bot }=\{0\}}$: If ${\displaystyle c\in C\cap C^{\bot }}$ then ${\displaystyle 0=\langle \,c,\,c\,\rangle =\|c\|^{2},}$ which implies ${\displaystyle c=0.}$ ${\displaystyle \blacksquare }$ Proof that ${\displaystyle C^{\bot }}$ is a closed vector subspace of ${\displaystyle H}$: Let ${\displaystyle P:=\prod _{c\in C}\mathbb {F} }$ where ${\displaystyle \mathbb {F} }$ is the underlying scalar field of ${\displaystyle H}$ and define $${\displaystyle {\begin{alignedat}{4}L:\,&H&&\to \,&&P\\&h&&\mapsto \,&&\left(\langle \,h,\,c\,\rangle \right)_{c\in C}\\\end{alignedat}}}$$ which is continuous and linear because this is true of each of its coordinates ${\displaystyle h\mapsto \langle h,c\rangle .}$ The set ${\displaystyle C^{\bot }=L^{-1}(0)=L^{-1}\left(\{0\}\right)}$ is closed in ${\displaystyle H}$ because ${\displaystyle \{0\}}$ is closed in ${\displaystyle P}$ and ${\displaystyle L:H\to P}$ is continuous. The kernel of any linear map is a vector subspace of its domain, which is why ${\displaystyle C^{\bot }=\ker L}$ is a vector subspace of ${\displaystyle H.}$ ${\displaystyle \blacksquare }$ Proof that ${\displaystyle C+C^{\bot }=H}$: Let ${\displaystyle x\in H.}$ The Hilbert projection theorem guarantees the existence of a unique ${\displaystyle m\in C}$ such that ${\displaystyle \|x-m\|\leq \|x-c\|{\text{ for all }}c\in C}$ (or equivalently, for all ${\displaystyle x-c\in x-C}$). Let ${\displaystyle p:=x-m}$ so that ${\displaystyle x=m+p\in C+p}$ and it remains to show that ${\displaystyle p\in C^{\bot }.}$ The inequality above can be rewritten as: $${\displaystyle \|p\|\leq \|z\|\quad {\text{ for all }}z\in x-C.}$$ Because ${\displaystyle m\in C}$ and ${\displaystyle C}$ is a vector space, ${\displaystyle m+C=C}$ and ${\displaystyle C=-C,}$ which implies that ${\displaystyle x-C=x+C=p+m+C=p+C.}$ The previous inequality thus becomes $${\displaystyle \|p\|\leq \|z\|\quad {\text{ for all }}z\in p+C.}$$ or equivalently, $${\displaystyle \|p\|\leq \|p+c\|\quad {\text{ for all }}c\in C.}$$ But this last statement is true if and only if ${\displaystyle \langle \,p,c\,\rangle =0}$ every ${\displaystyle c\in C.}$ Thus ${\displaystyle p\in C^{\bot }.}$ ${\displaystyle \blacksquare }$

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 ${\displaystyle C\subseteq H}$ and some ${\displaystyle x\in H,}$ define a function

$${\displaystyle d_{C,x}:C\to [0,\infty )\quad {\text{ by }}c\mapsto \|x-c\|.}$$

${\displaystyle d_{C,x},}$

${\displaystyle m}$

${\displaystyle \,\operatorname {domain} d_{C,x}=C\,}$

$${\displaystyle d_{C,x}(m)\,\leq \,d_{C,x}(c)\quad {\text{ for all }}c\in C,}$$

${\displaystyle d_{C,x}(m)=\|m-x\|}$

${\displaystyle d_{C,x},}$

$${\displaystyle \inf _{c\in C}d_{C,x}(c)=\inf _{c\in C}\|x-c\|.}$$

Effects of translations and scalings

When this global minimum point ${\displaystyle m}$ exists and is unique then denote it by ${\displaystyle \min(C,x);}$ explicitly, the defining properties of ${\displaystyle \min(C,x)}$ (if it exists) are:

$${\displaystyle \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.}$$

${\displaystyle C}$

${\displaystyle C}$

${\displaystyle x\in C}$

${\displaystyle \min(C,x)=x.}$

If ${\displaystyle C\subseteq H}$ is a non-empty subset, ${\displaystyle s}$ is any scalar, and ${\displaystyle x,x_{0}\in H}$ are any vectors then

$${\displaystyle \,\min \left(sC+x_{0},sx+x_{0}\right)=s\min(C,x)+x_{0}}$$

$${\displaystyle {\begin{alignedat}{6}\min &(sC,sx)&&=s&&\min(C,x)\\\min &(-C,-x)&&=-&&\min(C,x)\\\end{alignedat}}}$$

$${\displaystyle {\begin{alignedat}{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{alignedat}}}$$

$${\displaystyle {\begin{alignedat}{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{alignedat}}}$$

Examples

The following counter-example demonstrates a continuous linear isomorphism ${\displaystyle A:H\to H}$ for which ${\displaystyle \,\min(A(C),A(x))\neq A(\min(C,x)).}$ Endow ${\displaystyle H:=\mathbb {R} ^{2}}$ with the dot product, let ${\displaystyle x_{0}:=(0,1),}$ and for every real ${\displaystyle s\in \mathbb {R} ,}$ let ${\displaystyle L_{s}:=\{(x,sx):x\in \mathbb {R} \}}$ be the line of slope ${\displaystyle s}$ through the origin, where it is readily verified that ${\displaystyle \min \left(L_{s},x_{0}\right)={\frac {s}{1+s^{2}}}(1,s).}$ Pick a real number ${\displaystyle r\neq 0}$ and define ${\displaystyle A:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}$ by ${\displaystyle A(x,y):=(rx,y)}$ (so this map scales the ${\displaystyle x-}$coordinate by ${\displaystyle r}$ while leaving the ${\displaystyle y-}$coordinate unchanged). Then ${\displaystyle A:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}$ is an invertible continuous linear operator that satisfies ${\displaystyle A\left(L_{s}\right)=L_{s/r}}$ and ${\displaystyle A\left(x_{0}\right)=x_{0},}$ so that ${\displaystyle \,\min \left(A\left(L_{s}\right),A\left(x_{0}\right)\right)={\frac {s}{r^{2}+s^{2}}}(1,s)}$ and ${\displaystyle A\left(\min \left(L_{s},x_{0}\right)\right)={\frac {s}{1+s^{2}}}\left(r,s\right).}$ Consequently, if ${\displaystyle C:=L_{s}}$ with ${\displaystyle s\neq 0}$ and if ${\displaystyle (r,s)\neq (\pm 1,1)}$ then ${\displaystyle \,\min(A(C),A\left(x_{0}\right))\neq A\left(\min \left(C,x_{0}\right)\right).}$

See also

• Orthogonal complement – Concept in linear algebra
• Orthogonal projection – Idempotent linear transformation from a vector space to itselfPages displaying short descriptions of redirect targets
• Orthogonality principle – Condition for optimality of Bayesian estimator
• Riesz representation theorem – Theorem about the dual of a Hilbert space

Notes

References

Bibliography

• Rudin, Walter (1987). Real and Complex Analysis (Third ed.).
• Rudin, Walter (1991). Functional Analysis. International Series in Pure and Applied Mathematics. Vol. 8 (Second ed.). New York, NY: McGraw-Hill Science/Engineering/Math. ISBN 978-0-07-054236-5. OCLC 21163277.