Iterative Projektionsmethoden in Banachräumen
Dieses Projekt wurde gefördert aus Mitteln des Landes Tirol (Tiroler Wissenschaftsförderung).
Der erste Teil dieser Darstellung ist allgemeinverständlich gehalten. Weiter unten finden Sie eine wissenschaftliche Beschreibung.
Kurzzusammenfassung
In vielen technischen und naturwissenschaftlichen Anwendungen der Mathematik ist es notwendig einen Punkt zu finden, der gewisse Eigenschaften hat und möglichst nahe an einem gegebenen Punkt liegt. Beispiele für solche Anwendungen sind unterdrückung, digitale Filter und Computertomographie. Iterative Projektionsverfahren ermöglichen es einen solchen Punkt schnell und effizient zu berechnen. Manche Anwendungen verlangen die Verwendung eines Abstandsbegriffs, der nicht mit dem aus dem Alltag bekannten Abstand übereinstimmt. Dieses Projekt beschäftigt sich mit der Frage, ob auch in diesen Fällen eine Lösung schnell berechnet werden kann.
Andere Arten der Abstandsmessung
Wir betrachten nun ein Beispiel für einen solchen Abstandsbegriff, der nicht dem aus dem Alltag bekannten entspricht. Dieser wird als \(\ell_p\)-Norm bezeichnet. Für ein fixiertes \(p\) mit \(1\leq p <\infty\) betrachten wir für Punkte \[x=(x_1,\ldots,x_n) \qquad\text{und}\qquad y=(y_1,\ldots,y_n)\] den Abstand \[\|x-y\|_p = \Big(\sum_{k=1}^{n} |x_k-y_k|^p\Big)^{1/p},\] der für \(p=2\) mit dem aus dem Alltag bekannten Abstand übereinstimmt.
p = 2
In der obigen Grafik finden Sie in blau einen "Kreis" mit Radius 1 bezüglich des betrachteten Abstandsum den Nullpunkt. Rechts oben können Sie den Exponenten der Norm verändern. Wenn Sie die Maus über die Grafik bewegen, sehen Sie ein Lineal, das den Abstand des Cursors vom Nullpunkt in der \(\ell_p\)-Norm misst. Im Fall \(p=2\) erhalten Sie den aus dem Alltag gewohnten Abstandsbegriff.
Projektionen
Unter einer Projektion verstehen wir eine Abbildung, die zu einer gegebenen Menge jedem Punkt den Punkt mit gerinstem Abstand in der Menge zuordnet. Die folgende interaktive Abbildung illustiert dies für den Fall \(p=2\) am Beispiel eines Kreises und einer Geraden.
In der obigen Grafik befindet sich an der Mausposition der Punkt \(v\). Der Punkt \(a\) ist die Projektion von \(v\) auf den Kreis und der Punkt \(b\) die Projektion von \(v\) auf die eingezeichnete Gerade.
In höheren Dimensionen und für \(p\neq 2\) verhalten sich diese Projektionen deutlich anders. Die folgenden Animationen sollen diesen Sachverhalt verdeutlichen. In der linken Animation sehen Sie einen Punkt, der sich auf einem Kreis um eine Gerade bewegt. Um diesen Punkt sehen Sie eine "Kugel" für \(p=4\), die die Gerade berührt. Beachten Sie, dass sich der Berührpunkt bewegt, während er für eine Kugel (d.h. \(p=2\)) immer gleich bleiben würde. In der rechten Animation sehen Sie ein Punkt, der sich so um eine Gerade bewegt, dass der Berührpunkt mit der Geraden immer gleich bleibt. Dabei untersuchen wir, wann der Punkt sich durch die Ebene, die im rechten Winkel auf die Gerade steht bewegt. Immer wenn dies passiert, wechselt der Hintergrund die Farbe. Beachten Sie, dass sich im Fall \(p=2\) der Punkt immer auf dieser Ebene bewegt und nie durch die Ebene durchgehen würde.
Wissenschaftlichter Abstract
Iterative Projektionsmethoden erlauben es Projektionen auf einfache Mengen zu benutzen, um eine gegebene Projektion auf eine komplizierte Menge effizient zu berechnen. Beispielsweise lassen sich mit solchen Verfahren inverse Probleme oder Problemstellungen im Zusammenhang mit Computertomographie lösen. In Hilberträumen sind die Konvergenzeigenschaften dieser Methoden gut erforscht. Über Projektionsverfahren in Banachräumen weiß man deutlich weniger. Das alternierende Approximationsverfahren ist ein Verfahren zur effizienten Berechnung der Projektion auf die Summe von abgeschlossenen Unterräumen. Es ist bekannt, dass dieses konvergiert wenn die Summe abgeschlossen ist, aber die Konvergenzrate ist unbekannt. Im Gegensatz zum Hilbertraumfall konvergiert das alternierende Projektionsverfahren in Banachräumen im Allgemeinen nicht gegen die Projektion auf den Durchschnitt der Unterräume.
Ziele des Forschungsprojekts
Das Ziel dieses Projekts ist es, ein besseres Verständnis für die Konvergenzeigenschaften dieser beiden Methoden zu erlangen. Von besonderem Interesse ist die theoretische Konvergenzrate des alternierenden Approximationsverfahrens sowie die Frage, ob diese Konvergenzrate auch in der Praxis erreicht wird. Darüber hinaus soll die Größe der Menge der Punkte, für die das alternierende Projektionsverfahren gegen die Projektion auf den Durchschnitt konvergiert, bestimmt werden.
Aktivitäten des Projekts
Personen
Folgende Personen haben in diesem Projekt mitgearbeitet:
- Christian Bargetz (Projektleiter)
- Franz Luggin (1.8.2018–31.1.2019)
- Emir Medjic (5.3.2018–2.9.2018)
Konferenzteilnahmen und Vorträge
- Analysis Seminar 2018, Traunkirchen (8.–10.6.2018)
Vortrag: On the convergence of the alternating method (Emir Medjic) - Workshop on Nonlinear Analysis and Optimization, The Technion, Haifa, 20 August 2018
Vortrag: On the convergence of the alternating method in uniformly smooth and uniformly convex Banach spaces (Emir Medjic) - 47th Winter School on Abstract Analysis (12.–19.1.2019)
Vorträge:- Iterating projections of various types (Christian Bargetz)
- Alternating projections in Banach spaces (Franz Luggin)
- Analysis Seminar Innsbruck 15th-17th November 2019 (15.-17.11.2019 ) Posterpräsentation: On the convergence of iterated Bregman projections and of the alternating algorithm. (Emir Medjic)
- 48th Winter school on abstract analysis 2020 (11.-18.01. 2020)
Vortrag: On the Alternating Algorithm (Emir Medjic)
Im Projekt entstandene Publikationen
- C. Bargetz und E. Medjic: On the rate of convergence of iterated Bregman projections and of the alternating algorithm. J. Math. Anal. Appl. 481(1): Article 123482, 2020, DOI: 10.1016/j.jmaa.2019.123482, arXiv:1905.00605
- E. Medjic: The alternating algorithm. Masterarbeit. Universität Innsbruck. 2019
- F. Luggin: Metric Projections and the Alternating Projection Method in Banach Spaces. Masterarbeit. Universität Innsbruck. 2020