Effiziente Rekonstruktion von Funktionen mittels Eigenfunktionen linearer Operatoren
Zusammenfassung der Projektergebnisse
Die wichtigsten Resultate dieses Projektes beziehen sich auf drei Themengebiete, für die wir nichtlineare Algorithmen hergeleitet haben, mit denen Signale rekonstruiert werden können, die sich als M-Term Approximation von Eigenfunktionen linearer Operatoren darstellen lassen. 1. Mit Hilfe eines neuen iterativen Ansatzes gelang uns die Herleitung von deterministischen sublinearen FFT-Algorithmen zur Berechnung der diskreten Fourier-Transformation von Vektoren x ∈ CN mit nur m < N signifikant von Null verschiedenen Einträgen. Besonders stabile Algorithmen werden erhalten, wenn der zu berechnende Vektor einen Träger der Länge m besitzt, d.h., wenn alle signifikanten Einträge benachbart sind. In diesem Fall erhalten wir stabile Algorithmen mit der Komplexität O(m log2 N). Erweiterungen des Algorithmus benötigen keine a priori Kenntnis der Trägerlänge des zu berechnenden Vektors, sondern finden eine mögliche “Dünnbesetztheit” automatisch. Falls der gesuchte Vektor keinen kleinen Träger hat, fällt der Algorithmus auf die übliche FFT mit der Komplexität O(N log2 N ) zurück. 2. Wir konnten die verallgemeinerte Prony-Methode ausnutzen, um verschiedene Signalmodelle herzuleiten, wie zum Beispiel trigonometrische Funktionen, M-Term-Entwicklungen von verschobenen Gauss-Funktionen, Linearkombinationen von Monomen der Form xpj mit pj ∈ C, Chirp-Funktionen, M-Term-Entwicklungen orthogonaler Polynome usw. In vielen Fällen gelang es uns, die zu rekonstruierenden Funktionen als Eigenfunktionen verallgemeinerter Shift-Operatoren darzustellen, so dass eine Rekonstruktion der betrachteten nicht-stationären Signale aus einer geringen Anzahl von Funktionswerten möglich ist. 3. Außerdem haben wir uns mit verschiedenen Anwendungen der Prony-Methode beschäftigt. Wir konnten einen adaptiven Algorithmus zur Rekonstruktion von charakteristischen 2D-Funktionen mit polygonalem Träger herleiten, der nur 3N Fourier-Abtastwerte zur Bestimmung des (nicht notwendig konvexen) Polygons mit N Ecken benötigt. - Wir haben die Prony-Methode erfolgreich zur Phasenrekonstruktion eines dünn-besetzten eindimensionalen Signals aus den Fourier-Intensitäten eingesetzt. - In einem völlig anderen Kontext konnten wir mit Hilfe der Prony-Methode einen Algorithmus zur adaptiven Berechnung einer Takenaka-Malmquist Basis zur Darstellung einer periodischen reellwertigen Funktion in einer adaptiven Fourier-Reihe herleiten. Diese Basis führt zu exponentieller Konvergenz für Funktionen, deren klassische Fouriersummen nur polynomial konvergieren.
Projektbezogene Publikationen (Auswahl)
- Prony methods for recovery of structured functions, GAMM-Mitt. 37(2) (2014), 239–258
Gerlind Plonka and Manfred Tasche
(Siehe online unter https://doi.org/10.1002/gamm.201410011) - Prony’s Method for Multivariate Signals. Proc. Appl. Math. Mech. Volume 15, Issue 1, pp. 665–666, October 2015
Thomas Peter, Gerlind Plonka, and Robert Schaback
(Siehe online unter https://doi.org/10.1002/pamm.201510322) - A deterministic sparse FFT algorithm for vectors with small support, Numer. Algorithms 71(4) (2016), 889-905
Gerlind Plonka and Katrin Wannenwetsch
(Siehe online unter https://doi.org/10.1007/s11075-015-0028-0) - Reconstruction of polygonal shapes from sparse Fourier samples, J. Comput. Appl. Math. 297 (2016), 117–131
Marius Wischerhoff and Gerlind Plonka
(Siehe online unter https://doi.org/10.1016/j.cam.2015.11.013) - A sparse Fast Fourier algorithm for real nonnegative vectors, J. Comput. Appl. Math. 321 (2017), 532–539
Gerlind Plonka and Katrin Wannenwetsch
(Siehe online unter https://doi.org/10.1016/j.cam.2017.03.019) - Sparse phase retrieval of one-dimensional signals by Prony’s method, Frontiers Appl. Math. Stat. 3:5 (2017)
Robert Beinert and Gerlind Plonka
(Siehe online unter https://doi.org/10.3389/fams.2017.00005) - Deterministic sparse FFT for M-sparse vectors, Numer. Algorithms 78(1) (2018), 133–159
Gerlind Plonka, Katrin Wannenwetsch, Annie Cuyt, and Wen-Shin Lee
(Siehe online unter https://doi.org/10.1007/s11075-017-0370-5) - Computation of adaptive Fourier series by sparse approximation of exponential sums, J. Fourier Anal. Appl.
Gerlind Plonka and Vlada Pototskaia
(Siehe online unter https://doi.org/10.1007/s00041-018-9635-1) - Reconstruction of stationary and non-stationary signals by the generalized Prony method, Anal. Appl. 17(2) (2019), 179–210
Gerlind Plonka, Kilian Stampfer and Ingeborg Keller
(Siehe online unter https://doi.org/10.1142/S0219530518500240) - The generalized operator-based Prony method, Preprint 2019
Kilian Stampfer and Gerlind Plonka
(Siehe online unter https://doi.org/10.1007/s00365-020-09501-6)
