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 $${\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}}}$$ Since ${\displaystyle \partial c}$ is a vector in ${\displaystyle C}$ that represents an arbitrary tangent direction, it follows that ${\displaystyle m-x}$ must be orthogonal to every vector in ${\displaystyle C.}$

Statement

Detailed elementary proof

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.}$

Consequences

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\|.}$$ A global minimum point of ${\displaystyle d_{C,x},}$ if one exists, is any point ${\displaystyle m}$ in ${\displaystyle \,\operatorname {domain} d_{C,x}=C\,}$ such that $${\displaystyle d_{C,x}(m)\,\leq \,d_{C,x}(c)\quad {\text{ for all }}c\in C,}$$ in which case ${\displaystyle d_{C,x}(m)=\|m-x\|}$ is equal to the global minimum value of the function ${\displaystyle d_{C,x},}$ which is: $${\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.}$$ The Hilbert projection theorem guarantees that this unique minimum point exists whenever ${\displaystyle 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 ${\displaystyle C}$ is non-empty, if ${\displaystyle x\in C}$ then ${\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}}$$ which implies: $${\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.

1. Hilbert space
2. Projection (linear algebra)
3. Spectral theorem
4. Projection-valued measure
5. List of things named after David Hilbert
6. Gleason's theorem
7. Riesz representation theorem
8. Conditional expectation
9. List of theorems
10. Orthogonality principle
11. Hilbert transform
12. Pythagorean theorem
13. Convex optimization
14. Contraction (operator theory)
15. Kochen–Specker theorem
16. Min-max theorem
17. Orthogonal complement
18. No-communication theorem
19. Stinespring dilation theorem
20. Perron–Frobenius theorem