Efficient reconstruction of functions using eigenfunctions of linear operators
Final Report Abstract
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.
Publications
- Prony methods for recovery of structured functions, GAMM-Mitt. 37(2) (2014), 239–258
Gerlind Plonka and Manfred Tasche
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at https://doi.org/10.1142/S0219530518500240) - The generalized operator-based Prony method, Preprint 2019
Kilian Stampfer and Gerlind Plonka
(See online at https://doi.org/10.1007/s00365-020-09501-6)
