Efficient function reconstruction using eigenfunctions of linear operators

(2014 - 2019)

Individual research grant of the German Research Foundation Goal of this project is the generalization of nonlinear reconstruction methods that are based on Prony's method. Here we apply a new view on this approach, namely that the classical Prony method for parameter identification in exponential sums as well as the Ben-Or and Tiwari algorithm for sparse polynomial interpolation can be understood as nonlinear reconstruction techniques for M-term expansions of eigenfunctions of special linear operators. We are particularly interested in deriving fast and numerically stable reconstruction schemes as well as new error estimates in case of noisy input data.

Principal investigator: Gerlind Plonka-Hoch
Staff: Katrin Wannenwetsch, Markus Petz, Kilian Stampfer

Corresponding publications

• Computation of adaptive Fourier series by sparse approximation of exponential sums
  Gerlind Plonka, Vlada Pototskaia
  Journal of Fourier Analysis and Applications 25(4), pp. 1580–1608, 2019, preprint as download.
• Application of the AAK theory and Prony-like Methods for sparse approximation of exponential sums
  Vlada Pototskaia, Gerlind Plonka
  Proc. Appl. Math. Mech. Volume 17, pp. 835-836, December 2017, DOI 10.1002/pamm.20171038.
• Sparse phase retrieval of structured signals by Prony’s method
  Robert Beinert, Gerlind Plonka
  Proc. Appl. Math. Mech. Volume 15, Issue 1, pp. 829-830, December 2017, DOI 10.1002/pamm.201710382.
• A sparse Fast Fourier algorithm for real nonnegative vectors
  Gerlind Plonka, Katrin Wannenwetsch
  Journal of Computational and Applied Mathematics 321, 532-539, 2017, preprint as download.
• Deterministic Sparse FFT Algorithms
  Katrin Wannenwetsch
  Dissertation, 2016, published online on 30 September 2016, http://hdl.handle.net/11858/00-1735-0000-002B-7C10-0.
• Application of the AAK theory for sparse approximation of exponential sums
  Gerlind Plonka, Vlada Pototskaia
  working paper, 2016, preprint as download (arXiv).
• Sparse approximation by Prony's method and AAK theory
  Gerlind Plonka, Vlada Pototskaia
  Oberwolfach Reports, Volume 33, pp. 16-19, 2016, preprint as download.
• Reconstruction of polygonal shapes from sparse Fourier samples
  Marius Wischerhoff, Gerlind Plonka
  Journal of Computational and Applied Mathematics 297, 117-131, 2016, preprint as download.
• A deterministic sparse FFT algorithm for vectors with small support
  Gerlind Plonka, Katrin Wannenwetsch
  Numerical Algorithms 71(4), 889-905, 2016, preprint as download.
• Deterministic sparse FFT algorithms
  Gerlind Plonka, Katrin Wannenwetsch
  Proc. Appl. Math. Mech. Volume 15, Issue 1, pp. 667-668, October 2015, DOI: 10.1002/pamm.201510323, preprint as download.
• Prony's Method for Multivariate Signals
  Thomas Peter, Gerlind Plonka, Robert Schaback
  Proc. Appl. Math. Mech. Volume 15, Issue 1, pp. 665-666, October 2015, DOI: 10.1002/pamm.201510322, preprint as download.
• A deterministic sparse FFT algorithm for vectors with short support
  Gerlind Plonka, Katrin Wannenwetsch
  Oberwolfach Reports, Volume 38, pp. 41-44, 2015,
• Prony methods for recovery of structured functions
  Gerlind Plonka, M. Tasche
  GAMM-Mitt. 37(2), 2014, 239-258, revised preprint as download.

Corresponding software

• Sparse FFT (small support)
  A new deterministic sparse FFT algorithm for vectors with small support.
  Katrin Wannenwetsch, Gerlind Plonka
  
• Sparse FFT (real non-negative)
  A new deterministic sparse FFT algorithm for real non-negative vectors.
  Katrin Wannenwetsch, Gerlind Plonka