This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Hilbert projection theorem" – news ·newspapers ·books ·scholar ·JSTOR(February 2020)

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

Some intuition for the theorem can be obtained by considering thefirst 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 aminimizer orminimum point of the function${\displaystyle N:C\to \mathbb{R}}$ defined by${\displaystyle N(c):=\Vert c-x\Vert }$ (which is the same as the minimum point of${\displaystyle c\mapsto \Vert c-x{\Vert }^2}$), then derivative must be zero at${\displaystyle m.}$

In matrix derivative notation:^[1]Since${\displaystyle \mathrm{\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.}$

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

Let${\displaystyle \delta :=\underset{c\in C}{inf}\Vert x-c\Vert }$ be the distance between${\displaystyle x}$ and${\displaystyle C,}$${\displaystyle {\left(c_n\right)}_{n=1}^{\mathrm{\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 {\Vert c_n-c_m\Vert }^2={\Vert c_n-x\Vert }^2+{\Vert c_m-x\Vert }^2-2⟨c_n-x,c_m-x⟩}$$and$${\displaystyle 4{\Vert \frac{c_n+c_m}{2}-x\Vert }^2={\Vert c_n-x\Vert }^2+{\Vert c_m-x\Vert }^2+2⟨c_n-x,c_m-x⟩}$$Therefore$${\displaystyle {\Vert c_n-c_m\Vert }^2=2{\Vert c_n-x\Vert }^2+2{\Vert c_m-x\Vert }^2-4{\Vert \frac{c_n+c_m}{2}-x\Vert }^2}$$(This equation is the same asthe formula${\displaystyle a^2=2b^2+2c^2-4M_a^2}$ for the length${\displaystyle M_a}$ of amedian 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 midpoint 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 \Vert c_n-c_m{\Vert }^2\le 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}^{\mathrm{\infty }}}$ is aCauchy 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 ◼}$

Proof that${\displaystyle m}$ is unique

Let${\displaystyle m_1}$ and${\displaystyle m_2}$ be twominimum points. Then:$${\displaystyle \Vert m_2-m_1{\Vert }^2=2\Vert m_1-x{\Vert }^2+2\Vert m_2-x{\Vert }^2-4{\Vert \frac{m_1+m_2}{2}-x\Vert }^2}$$

Since${\displaystyle \frac{m_1+m_2}{2}}$ belongs to${\displaystyle C,}$ we have${\displaystyle {\Vert \frac{m_1+m_2}{2}-x\Vert }^2\ge {\delta }^2}$ and therefore$${\displaystyle \Vert m_2-m_1{\Vert }^2\le 2{\delta }^2+2{\delta }^2-4{\delta }^2=0.}$$

Hence${\displaystyle m_1=m_2,}$ which proves uniqueness.${\displaystyle ◼}$

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 ⟨m-x,c⟩=0}$ for every${\displaystyle c\in C.}$

Proof that the condition is sufficient: Let${\displaystyle z\in C}$ be such that${\displaystyle ⟨z-x,c⟩=0}$ for all${\displaystyle c\in C.}$ If${\displaystyle c\in C}$ then${\displaystyle c-z\in C}$ and so$${\displaystyle \Vert c-x{\Vert }^2=\Vert (z-x)+(c-z){\Vert }^2=\Vert z-x{\Vert }^2+\Vert c-z{\Vert }^2+2⟨z-x,c-z⟩=\Vert z-x{\Vert }^2+\Vert c-z{\Vert }^2}$$ which implies that${\displaystyle \Vert z-x{\Vert }^2\le \Vert c-x{\Vert }^2.}$ Because${\displaystyle c\in C}$ was arbitrary, this proves that${\displaystyle \Vert z-x\Vert =\underset{c\in C}{inf}\Vert c-x\Vert }$ 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 \Vert m-x\Vert \le \Vert (m+tc)-x\Vert .}$ Thus$${\displaystyle \Vert (m+tc)-x{\Vert }^2-\Vert m-x{\Vert }^2=2t⟨m-x,c⟩+t^2\Vert c{\Vert }^2}$$is always non-negative and${\displaystyle ⟨m-x,c⟩}$ must be a real number. If${\displaystyle ⟨m-x,c⟩\ne 0}$ then the map${\displaystyle f(t):=2t⟨m-x,c⟩+t^2\Vert c{\Vert }^2}$ has a minimum at${\displaystyle t_0:=-\frac{⟨m-x,c⟩}{\Vert c{\Vert }^2}}$ and moreover, which is a contradiction. Thus${\displaystyle ⟨m-x,c⟩=0.}$${\displaystyle ◼}$

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:=\underset{c\in C}{inf}\Vert c\Vert .}$$This theorem will follow from the following lemmas.

Lemma 1—If${\displaystyle c_{\bullet }:={\left(c_n\right)}_{n=1}^{\mathrm{\infty }}}$ isany sequence in${\displaystyle C}$ such that${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\Vert c_n\Vert =d}$ in${\displaystyle \mathbb{R}}$ then there exists some${\displaystyle c\in C}$ such that${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{c}_n=c}$ in${\displaystyle H.}$ Furthermore,${\displaystyle \Vert c\Vert =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\le \Vert \frac{1}{2}\left(c_m+c_n\right)\Vert ,}$ which implies that${\displaystyle 4d^2\le {\Vert c_m+c_n\Vert }^2.}$ By theparallelogram law,$${\displaystyle {\Vert c_m+c_n\Vert }^2+{\Vert c_m-c_n\Vert }^2=2{\Vert c_m\Vert }^2+2{\Vert c_n\Vert }^2}$$where${\displaystyle 4d^2\le {\Vert c_m+c_n\Vert }^2}$ now implies$${\displaystyle 4d^2+{\Vert c_m-c_n\Vert }^2\le 2{\Vert c_m\Vert }^2+2{\Vert c_n\Vert }^2}$$and so$${\displaystyle \begin{array}{r}{\Vert c_m-c_n\Vert }^2\le 2{\Vert c_m\Vert }^2+2{\Vert c_n\Vert }^2-4d^2\end{array}}$$The assumption${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\Vert c_n\Vert =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 {\Vert c_m-c_n\Vert }^2}$ and thus also of${\displaystyle \Vert c_m-c_n\Vert ,}$ which proves that${\displaystyle {\left(c_n\right)}_{n=1}^{\mathrm{\infty }}}$ is a Cauchy sequence in${\displaystyle H.}$ Since${\displaystyle H}$ is complete, there exists some${\displaystyle c\in H}$ such that${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{c}_n=c}$ in${\displaystyle H.}$ Because every${\displaystyle c_n}$ belongs to${\displaystyle C,}$ which is aclosed 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 \Vert \cdot \Vert :H\to \mathbb{R}}$ is a continuous function,${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{c}_n=c}$ in${\displaystyle H}$ implies that${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\Vert c_n\Vert =\Vert c\Vert }$ in${\displaystyle \mathbb{R}.}$ But${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\Vert c_n\Vert =d}$ also holds (by assumption) so that${\displaystyle \Vert c\Vert =d}$ (because limits in${\displaystyle \mathbb{R}}$ are unique).${\displaystyle ◼}$

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

Proof of Lemma 2

The existence of the sequence follows from the definition of theinfimum, as is now shown. The set${\displaystyle S:=\{\Vert c\Vert :c\in C\}}$ is a non-empty subset of non-negative real numbers and${\displaystyle d:=\underset{c\in C}{inf}\Vert c\Vert =infS.}$ Let${\displaystyle n\ge 1}$ be an integer. Because there exists some${\displaystyle s_n\in S}$ such that Since${\displaystyle s_n\in S,}$${\displaystyle d=infS\le s_n}$ holds (by definition of the infimum). Thus and now thesqueeze theorem implies that${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{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:=\underset{s\in S}{inf}s}$ is finite). For every${\displaystyle n\in \mathbb{N},}$ the fact that${\displaystyle s_n\in S=\{\Vert c\Vert :c\in C\}}$ means that there exists some${\displaystyle c_n\in C}$ such that${\displaystyle s_n=\Vert c_n\Vert .}$ The convergence${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{s}_n=d}$ in${\displaystyle \mathbb{R}}$ thus becomes${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\Vert c_n\Vert =d}$ in${\displaystyle \mathbb{R}.}$${\displaystyle ◼}$

Lemma 2 and Lemma 1 together prove that there exists some${\displaystyle c\in C}$ such that${\displaystyle \Vert c\Vert =d.}$ Lemma 1 can be used to prove uniqueness as follows. Suppose${\displaystyle b\in C}$ is such that${\displaystyle \Vert b\Vert =d}$ and denote the sequence$${\displaystyle b,c,b,c,b,c,\dots }$$ by${\displaystyle {\left(c_n\right)}_{n=1}^{\mathrm{\infty }}}$ so that thesubsequence${\displaystyle {\left(c_{2n}\right)}_{n=1}^{\mathrm{\infty }}}$ of even indices is the constant sequence${\displaystyle c,c,c,\dots }$ while the subsequence${\displaystyle {\left(c_{2n-1}\right)}_{n=1}^{\mathrm{\infty }}}$ of odd indices is the constant sequence${\displaystyle b,b,b,\dots .}$ Because${\displaystyle \Vert c_n\Vert =d}$ for every${\displaystyle n\in \mathbb{N},}$${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\Vert c_n\Vert =\underset{n\to \mathrm{\infty }}{lim}d=d}$ in${\displaystyle \mathbb{R},}$ which shows that the sequence${\displaystyle {\left(c_n\right)}_{n=1}^{\mathrm{\infty }}}$ satisfies the hypotheses of Lemma 1. Lemma 1 guarantees the existence of some${\displaystyle x\in C}$ such that${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{c}_n=x}$ in${\displaystyle H.}$ Because${\displaystyle {\left(c_n\right)}_{n=1}^{\mathrm{\infty }}}$ converges to${\displaystyle x,}$ so do all of its subsequences. In particular, the subsequence${\displaystyle c,c,c,\dots }$ 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,\dots }$ converges to both${\displaystyle x}$ and${\displaystyle b.}$ Thus${\displaystyle b=c,}$ which proves the theorem.${\displaystyle ◼}$

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${\displaystyle C\subseteq H}$ and some${\displaystyle x\in H,}$ define a function$${\displaystyle d_{C,x}:C\to [0,\mathrm{\infty })\text{ by }c\mapsto \Vert x-c\Vert .}$$ Aglobal minimum point of${\displaystyle d_{C,x},}$ if one exists, is any point${\displaystyle m}$ in${\displaystyle \mathrm{domain}{d}_{C,x}=C}$ such that$${\displaystyle d_{C,x}(m)\le d_{C,x}(c)\text{ for all }c\in C,}$$ in which case${\displaystyle d_{C,x}(m)=\Vert m-x\Vert }$ is equal to theglobal minimum value of the function${\displaystyle d_{C,x},}$ which is:$${\displaystyle \underset{c\in C}{inf}{d}_{C,x}(c)=\underset{c\in C}{inf}\Vert x-c\Vert .}$$

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\text{ and }\Vert x-min(C,x)\Vert \le \Vert x-c\Vert \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)=smin(C,x)+x_0}$$which implies:

Examples

The following counter-example demonstrates a continuous linear isomorphism${\displaystyle A:H\to H}$ for which${\displaystyle min(A(C),A(x))\ne A(min(C,x)).}$ Endow${\displaystyle H:={\mathbb{R}}^2}$ with thedot 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\ne 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\ne 0}$ and if${\displaystyle (r,s)\ne (\pm 1,1)}$ then${\displaystyle min(A(C),A\left(x_0\right))\ne A\left(min\left(C,x_0\right)\right).}$

For any closed convex nonempty subset${\displaystyle C\subset H}$, let${\displaystyle P_C:H\to C}$ be the projection function.

If there are multiple closed convex subsets${\displaystyle C_1,C_2,\dots ,C_n}$, then one can approximate the projection operator${\displaystyle P_{C_1\cap \cdots \cap C_n}}$ by applying${\displaystyle P_{C_1},P_{C_2},\dots ,P_{C_n}}$ in sequence, then do it again and again. That is, one can approximate${\displaystyle (P_{C_n}\dots P_{C_2}{P}_{C_1}{)}^k\to P_{C_1\cap \cdots \cap C_n}}$ as${\displaystyle k\to \mathrm{\infty }}$. TheKaczmarz method is a commonly used special case. Such methods can be computationally effective. For example, if${\displaystyle C}$ is a complicated shape, then projecting directly to${\displaystyle C}$ may be difficult. However,${\displaystyle C}$ can be approximated as an intersection of simple objects likehalf-spaces,hyperplanes, finite-dimensional subspaces, orcones.^[4]

If${\displaystyle C}$ is a closed subspace, then it is convex. In this case, the projection function${\displaystyle P:H\to C}$ is an orthogonal projection (a continuous linear operator that is self-adjoint). A classic theorem states that, if${\displaystyle C_1,\dots ,C_n}$ are closed subspaces, then^[5]$${\displaystyle \underset{k\to \mathrm{\infty }}{lim}\Vert (P_{C_1}\cdots P_{C_n}{)}^{k}x-P_{C_1\cap \cdots \cap C_n}x\Vert =0,\mathrm{\forall }x\in H}$$

• 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

• 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.

• Convex analysis
• Theorems in functional analysis

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from February 2020
• All articles needing additional references
• Pages displaying short descriptions of redirect targets via Module:Annotated link