Effiziente Rekonstruktion von Funktionen mittels Eigenfunktionen linearer Operatoren

• Antragstellerin: Professorin Dr. Gerlind Plonka-Hoch
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2013 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 244772350

• Erstellungsjahr: 2019

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
  
• 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
  
• A deterministic sparse FFT algorithm for vectors with small support, Numer. Algorithms 71(4) (2016), 889-905
  Gerlind Plonka and Katrin Wannenwetsch
  
• Reconstruction of polygonal shapes from sparse Fourier samples, J. Comput. Appl. Math. 297 (2016), 117–131
  Marius Wischerhoff and Gerlind Plonka
  
• A sparse Fast Fourier algorithm for real nonnegative vectors, J. Comput. Appl. Math. 321 (2017), 532–539
  Gerlind Plonka and Katrin Wannenwetsch
  
• Sparse phase retrieval of one-dimensional signals by Prony’s method, Frontiers Appl. Math. Stat. 3:5 (2017)
  Robert Beinert and Gerlind Plonka
  
• Deterministic sparse FFT for M-sparse vectors, Numer. Algorithms 78(1) (2018), 133–159
  Gerlind Plonka, Katrin Wannenwetsch, Annie Cuyt, and Wen-Shin Lee
  
• Computation of adaptive Fourier series by sparse approximation of exponential sums, J. Fourier Anal. Appl.
  Gerlind Plonka and Vlada Pototskaia
  
• 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
  
• The generalized operator-based Prony method, Preprint 2019
  Kilian Stampfer and Gerlind Plonka