Hilbert-Projektionssatz: Dimensionen in der Computer Vision erschließen

Von Fouad Sabry

Was ist der Hilbert-Projektionssatz?

In der Mathematik ist der Hilbert-Projektionssatz ein berühmtes Ergebnis der Konvexanalyse, der besagt, dass es für jeden Vektor in einem Hilbert-Raum und für jede nichtleere geschlossene Konvexheit einen eindeutigen Vektor gibt, für den über die Vektoren minimiert wird; das heißt, so dass für jeden

Wie Sie davon profitieren

(I) Erkenntnisse und Validierungen zu den folgenden Themen:

Kapitel 1: Hilbert-Projektionssatz

Kapitel 2: Banachraum

Kapitel 3: Innerer Produktraum

Kapitel 4: Riesz-Darstellungssatz

Kapitel 5: Selbstadjungierter Operator

Kapitel 6: Trace-Klasse

Kapitel 7: Operator (Physik)

Kapitel 8: Hilbertraum

Kapitel 9: Norm (Mathematik)

Kapitel 10: Konvexe Analyse

(II) Beantwortung der häufigsten öffentlichen Fragen zum Hilbert-Projektionssatz.

(III) Beispiele aus der Praxis für die Verwendung des Hilbert-Projektionssatzes in vielen Bereichen.

Für wen dieses Buch ist

Fachleute, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über das Grundwissen oder die Informationen zum Hilbert-Projektionssatz hinausgehen möchten.

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 5. Mai 2024

Buchvorschau

Kapitel 1: Hilbert-Projektionstheorem

In der Mathematik ist der Satz der Hilbert-Projektion ein berühmtes Ergebnis der konvexen Analysis, die besagt, dass es für jeden Vektor x in einem Hilbertraum H und für jeden nichtleeren geschlossenen Konvex {\displaystyle C\subseteq H,} einen eindeutigen Vektor gibt {\displaystyle m\in C} , für  den {\displaystyle \|c-x\|} über  die Vektoren minimiert wird c\in C , d.h. so, dass {\displaystyle \|m-x\|\leq \|c-x\|} für jeden {\displaystyle c\in C.}

Durch die Betrachtung der Bedingung erster Ordnung des Optimierungsproblems kann man einen Einblick in das Theorem gewinnen.

Betrachten Sie einen endlichdimensionalen reellen Hilbertraum H mit einem Unterraum C und einem Punkt x. Wenn {\displaystyle m\in C} ein Minimierungs- oder Minimalpunkt der Funktion {\displaystyle N:C\to \mathbb {R} } ist, die durch definiert ist {\displaystyle N(c):=\|c-x\|} (was mit dem Minimalpunkt von {\displaystyle c\mapsto \|c-x\|^{2}} identisch ist), dann muss die Ableitung Null bei m.

Notation für Matrixableitungen

{\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}}}

Da {\displaystyle \partial c} ein Vektor in C ist, der eine beliebige Tangentenrichtung darstellt, folgt daraus, dass {\displaystyle m-x} orthogonal zu jedem Vektor in {\displaystyle C.}

Satz der Hilbert-Projektion — Für jeden Vektor x in einem Hilbertraum H und jede nichtleere geschlossene Konvex {\displaystyle C\subseteq H,} existiert ein eindeutiger Vektor {\displaystyle m\in C} , für den {\displaystyle \lVert x-m\rVert } gleich ist {\displaystyle \delta :=\inf _{c\in C}\|x-c\|.}

Wenn die geschlossene Teilmenge C auch ein vektorieller Unterraum von ist H , dann ist dieser Minimizer m das einzige Element in C solchem, das {\displaystyle m-x} orthogonal zu {\displaystyle C.}

Nachweis, dass eine Mindestpunktzahl y vorhanden ist

Sei {\displaystyle \delta :=\inf _{c\in C}\|x-c\|} der Abstand zwischen x und {\displaystyle C,} {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} einer Folge in einer C solchen Weise, dass der Abstand zum Quadrat zwischen x und c_{n} kleiner oder gleich {\displaystyle \delta ^{2}+1/n.} Sei Let n und m zwei ganze Zahlen, dann gilt die nachfolgende Gleichheit:

{\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 }

und

{\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 }

Deshalb

{\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}}

(Diese Gleichung ist identisch mit der Formel {\displaystyle a^{2}=2b^{2}+2c^{2}-4M_{a}^{2}} für die Länge M_a eines Medians in einem Dreieck mit Seiten der Länge a, b, und c, wobei genau die Eckpunkte des Dreiecks sind). {\displaystyle x,c_{m},c_{n}}

Indem man den ersten beiden Gliedern der Gleichheit eine obere Schranke gibt und feststellt, dass die Mitte von c_{n} und c_{m} zu und C daher einen Abstand größer oder gleich von \delta x, ihr hat, folgt:

{\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)}

Die letzte Ungleichung beweist, dass es {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} sich um eine Cauchy-Folge handelt.

Da C vollständig ist, ist die Sequenz also konvergent zu einem Punkt, {\displaystyle m\in C,} dessen Abstand von x minimal ist.

\blacksquare

Ein Beweis, der m einzigartig ist

Seien und m_{1} m_{2} zwei Mindestpunkte.

Dann:

{\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}}

Da {\displaystyle {\frac {m_{1}+m_{2}}{2}}} gehören {\displaystyle C,} wir und {\displaystyle \left\|{\frac {m_{1}+m_{2}}{2}}-x\right\|^{2}\geq \delta ^{2}} deshalb

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

Das {\displaystyle m_{1}=m_{2},} beweist Einzigartigkeit.

\blacksquare

Beweis der Charakterisierung des minimalen Punktes, wenn C ein geschlossener vektorieller Unterraum ist

Nehmen wir an, dass C es sich um einen geschlossenen vektoriellen Unterraum von H. Es muss gezeigt werden, dass der Minimizer m das eindeutige Element ist C , so dass {\displaystyle \langle m-x,c\rangle =0} für jede {\displaystyle c\in C.}

Beweis, dass die Bedingung ausreichend ist: Sei {\displaystyle z\in C} so, dass {\displaystyle \langle z-x,c\rangle =0} für alle {\displaystyle c\in C.} Wenn c\in C dann {\displaystyle c-z\in C} und 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}}

was impliziert, dass {\displaystyle \|z-x\|^{2}\leq \|c-x\|^{2}.} Weil c\in C willkürlich war, dies beweist, dass {\displaystyle \|z-x\|=\inf _{c\in C}\|c-x\|} und so z ist ein Minimalpunkt.

Nachweis, dass die Bedingung notwendig ist: Sei {\displaystyle m\in C} der Mindestpunkt.

Lassen c\in C und {\displaystyle t\in \mathbb {R} .} Weil {\displaystyle m+tc\in C,} die Minimalität der Garantien m so ist, dass

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

ist immer nicht negativ und {\displaystyle \langle m-x,c\rangle } muss eine reelle Zahl sein.

Wenn {\displaystyle \langle m-x,c\rangle \neq 0} dann hat die Karte

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

ein Minimum an {\displaystyle t_{0}:=-{\frac {\langle m-x,c\rangle }{\|c\|^{2}}}} und darüber hinaus, {\displaystyle f\left(t_{0}\right)<0,} was ein Widerspruch ist.

So {\displaystyle \langle m-x,c\rangle =0.} \blacksquare

Es genügt, den Satz zu beweisen, wenn der x=0 allgemeine Fall aus der folgenden Aussage folgt, indem  man C durch {\displaystyle C-x.}

Hilbert-Projektionssatz (Fall x=0 ) — Für jede nichtleere geschlossene konvexe Teilmenge {\displaystyle C\subseteq H} eines Hilbertraums H, existiert ein eindeutiger Vektor {\displaystyle m\in C} , so dass {\displaystyle \inf _{c\in C}\|c\|=\|m\|.}

Darüber hinaus ist das Zulassen {\displaystyle d:=\inf _{c\in C}\|c\|,} von if {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} eine beliebige Sequenz in C der Weise, dass {\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=d} in \mathbb {R} dann {\displaystyle \lim _{n\to \infty }c_{n}=m} in H.

Beweis

Sei C so, wie es in diesem Satz beschrieben ist, und sei

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

Dieser Satz ergibt sich aus den nachfolgenden Lemmas.

Lemma 1 — {\displaystyle c_{\bullet }:=\left(c_{n}\right)_{n=1}^{\infty }} Ist eine Folge in C derart, dass {\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=d} in \mathbb {R} dann existiert eine solche c\in C , dass {\displaystyle \lim _{n\to \infty }c_{n}=c} in H. Des Weiteren ist {\displaystyle \|c\|=d.}

Lemma 2 — Es existiert eine Sequenz {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} , die die Hypothesen von Lemma 1 erfüllt.

Lemma 2 und Lemma 1 beweisen zusammen, dass es welche gibt c\in C , so dass {\displaystyle \|c\|=d.} Lemma 1 verwendet werden kann, um die Eindeutigkeit wie folgt zu beweisen.

Angenommen {\displaystyle b\in C} , ist so, dass {\displaystyle \|b\|=d} und bezeichnen Sie die Sequenz

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

indem die {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} Teilfolge {\displaystyle \left(c_{2n}\right)_{n=1}^{\infty }} der geraden Indizes die konstante Folge ist {\displaystyle c,c,c,\ldots } , während die Teilfolge {\displaystyle \left(c_{2n-1}\right)_{n=1}^{\infty }} der ungeraden Indizes die konstante Folge ist {\displaystyle b,b,b,\ldots .} , weil {\displaystyle \left\|c_{n}\right\|=d} für jedes {\displaystyle n\in \mathbb {N} ,} {\displaystyle \lim _{n\to \infty }\left\|c_{n}\right\|=\lim _{n\to \infty }d=d} in {\displaystyle \mathbb {R} ,} zeigt, dass die Folge {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} die Hypothesen von Lemma 1 erfüllt.

Lemma 1 garantiert die Existenz von einigen x \in C , so dass {\displaystyle \lim _{n\to \infty }c_{n}=x} in H. Weil {\displaystyle \left(c_{n}\right)_{n=1}^{\infty }} konvergiert, um x, alle seine Unterfolgen zu konvergieren.

Insbesondere konvergiert {\displaystyle c,c,c,\ldots } die Teilfolge  gegen x, die impliziert, dass x=c (da die Grenzwerte in H eindeutig sind und diese konstante Teilfolge auch gegen konvergiert). c

Ebenso, x=b weil die Teilfolge {\displaystyle b,b,b,\ldots } gegen beide konvergiert x ,  {\displaystyle b.} was den Satz beweist. {\displaystyle b=c,}

\blacksquare

Proposition — Wenn C ein geschlossener vektorieller Unterraum eines Hilbertraums ist H , dann

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

Ausdruck als minimale globale

Die Aussage und Schlussfolgerung des Hilbert-Projektionssatzes kann in Bezug auf die globalen Minimums der unten aufgeführten Funktionen geschrieben werden. Darüber hinaus wird ihre Notation verwendet, um bestimmte Sätze zu vereinfachen.

Gegeben ist eine nicht-leere Teilmenge {\displaystyle C\subseteq H} und einige {\displaystyle x\in H,} definieren eine Funktion

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

Ein globaler Minimalpunkt von {\displaystyle d_{C,x},} wenn einer existiert, ist ein beliebiger Punkt m in {\displaystyle \,\operatorname {domain} d_{C,x}=C\,} derart, dass

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

in diesem Fall {\displaystyle d_{C,x}(m)=\|m-x\|} gleich dem globalen Minimalwert der Funktion {\displaystyle d_{C,x},} ist, der wie folgt lautet:

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

Translations- und Skalierungseffekte

Wenn dieser globale Minimalpunkt m existiert und eindeutig ist, dann bezeichnen Sie ihn explizit, indem {\displaystyle \min(C,x);} die definierenden Eigenschaften von {\displaystyle \min(C,x)} (falls vorhanden) sind:

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

Das Hilbert-Projektionstheorem garantiert, dass dieser eindeutige Minimalpunkt immer dann existiert, wenn C es sich um eine nicht-leere geschlossene und konvexe Teilmenge eines Hilbertraums handelt.

Dieser Minimalpunkt kann jedoch auch in nicht-konvexen oder offenen Teilmengen auftreten, z.B. solange er C nicht leer ist, wenn x \in C dann {\displaystyle \min(C,x)=x.}

Wenn {\displaystyle C\subseteq H} eine nicht-leere Teilmenge ist, s ein beliebiger Skalar ist und {\displaystyle x,x_{0}\in H} beliebige Vektoren sind, dann

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

Das bedeutet:

{\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}}}

Beispiele

Das folgende Gegenbeispiel zeigt einen kontinuierlichen linearen Isomorphismus {\displaystyle A:H\to H} , für den

{\displaystyle \,\min(A(C),A(x))\neq A(\min(C,x)).}

Endow {\displaystyle H:=\mathbb {R} ^{2}} mit dem Punktprodukt, sei {\displaystyle x_{0}:=(0,1),} und für jede reelle {\displaystyle s\in \mathbb {R} ,} Sei {\displaystyle L_{s}:=\{(x,sx):x\in \mathbb {R} \}} die Steigungslinie s durch den Ursprung, wobei leicht verifiziert werden kann, dass

{\displaystyle \min \left(L_{s},x_{0}\right)={\frac {s}{1+s^{2}}}(1,s).}

Wählen Sie eine reelle Zahl r\neq 0 und definieren {\displaystyle A:\mathbb {R} ^{2}\to \mathbb {R} ^{2}} Sie durch {\displaystyle A(x,y):=(rx,y)} (diese Abbildung skaliert also die {\displaystyle x-} Koordinate um r und lässt die {\displaystyle y-} Koordinate unverändert).

Dann {\displaystyle A:\mathbb {R} ^{2}\to \mathbb {R} ^{2}} ist ein invertierbarer kontinuierlicher linearer Operator, der und {\displaystyle A\left(L_{s}\right)=L_{s/r}} {\displaystyle A\left(x_{0}\right)=x_{0},} so erfüllt, dass

{\displaystyle \,\min \left(A\left(L_{s}\right),A\left(x_{0}\right)\right)={\frac {s}{r^{2}+s^{2}}}(1,s)}

und

{\displaystyle A\left(\min \left(L_{s},x_{0}\right)\right)={\frac {s}{1+s^{2}}}\left(r,s\right).}

Folglich, wenn {\displaystyle C:=L_{s}} mit s\neq 0 und wenn {\displaystyle (r,s)\neq (\pm 1,1)} dann

{\displaystyle \,\min(A(C),A\left(x_{0}\right))\neq A\left(\min \left(C,x_{0}\right)\right).}

{Ende Kapitel 1}

Kapitel 2: Siehe auch Konvexität in der Volkswirtschaftslehre – Bedeutendes Thema in der Volkswirtschaftslehre Nichtkonvexität (Volkswirtschaftslehre) – Verletzungen der Konvexitätsannahmen der elementaren Volkswirtschaftslehre Liste der Konvexitätsthemen Werner Fenchel – Deutscher Mathematiker Notizen ^ a b Rockafellar, R. Tyrrell (1997) [1970]. Konvexe Analyse. Princeton, NJ: Princeton University Press. ISBN 978-0-691-01586-6. ^ a b c Rockafellar & Wets 2009, S. 1–28. ^ a b Zălinescu 2002, S. 75–79. ^ Borwein, Jonathan; Lewis, Adrian (2006). Konvexe Analysis und nichtlineare Optimierung: Theorie und Beispiele (2. Aufl.). Springer. S. 76–77. ISBN 978-0-387-29570-1. ^ a b Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai (2009). Dualität in der Vektoroptimierung. Springer. ISBN 978-3-642-02885-4. ^ Zălinescu 2002, S. 106–113. ^ Csetnek, Ernö Robert (2010). Überwindung des Versagens der klassischen verallgemeinerten inneren Punkt-Regularitätsbedingungen in der konvexen Optimierung. Anwendung der Dualitätstheorie auf Vergrößerungen von maximalen monotonen Operatoren. Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3. ^ Borwein, Jonathan; Lewis, Adrian (2006). Konvexe Analysis und nichtlineare Optimierung: Theorie und Beispiele (2. Aufl.). Springer. ISBN 978-0-387-29570-1. ^ Boyd, Stephan; Vandenberghe, Lieven (2004). Konvexe Optimierung (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Abgerufen am 3. Oktober 2011. ^ Die Schlussfolgerung ist sofort, wenn {\displaystyle X=\{0\}}, also nehmen Sie etwas anderes an. Fix {\displaystyle x\in X.} Das Ersetzen von f durch die Norm ergibt {\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},z\right\rangle -\|z\|{ \text{ für alle }}z\in X\right\}.} Wenn {\displaystyle x^{*}\in \partial f(x)} und r \geq 0 reell ist, dann ergibt die Verwendung von {\displaystyle z:=rx} {\displaystyle \left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},rx\right\rangle -\|rx\|=r\left[\left\langle x^{*},x\right\rangle -\|x\|\right],} wobei insbesondere die Verwendung von {\displaystyle r:=2} {\displaystyle x^{*}(x)\geq \|x\|} ergibt, während {\displaystyle r:={\frac {1}{2}}} ergibt {\displaystyle x^{*}(x)\leq \|x\|} und damit {\displaystyle x^{*}(x)=\|x\|} ; Außerdem, wenn zusätzlich x\neq 0 ist, dann weil {\displaystyle x^{*}\left({\frac {x}{\|x\|}} \right)=1,} Aus der Definition der dualen Norm folgt, dass {\displaystyle \left\|x^{*}\right\|\geq 1.} Da {\displaystyle \partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},} ist, was äquivalent zu {\displaystyle \partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},} folgt, dass {\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|{ \text{ und }}\|z\|\geq \left\langle x^{*},z\right\rangle {\text{ for all }}z\in X\right\},}, was {\displaystyle \left\|x^{*}\right\|\leq 1} für alle {\displaystyle x^{*}\in \partial f(x) impliziert.} Aus diesen Tatsachen kann nun die Schlussfolgerung gezogen werden. ∎ Referenzen Bauschke, Heinz H.; Combettes, Patrick L. (28. Februar 2017). Konvexe Analysis und monotone Operatortheorie in Hilberträumen. CMS-Bücher in Mathematik. Springer Science & Business Media. ISBN 978-3-319-48311-5. OCLC 1037059594. Boyd, Stephen; Vandenberghe, Lieven (8. März 2004). Konvexe Optimierung. Cambridge-Reihe in statistischer und probabilistischer Mathematik. Cambridge, Vereinigtes Königreich New York: Cambridge