Exact Reconstruction of Sparse Non-Harmonic Signals from Fourier Coefficients

Markus Petz, Gerlind Plonka, Nadiia Derevianko

Published 2020-11-26Version 1

In this paper, we derive a new reconstruction method for real non-harmonic Fourier sums, i.e., real signals which can be represented as sparse exponential sums of the form $f(t) = \sum_{j=1}^{K} \gamma_{j} \, \cos(2\pi a_{j} t + b_{j})$, where the frequency parameters $a_{j} \in {\mathbb R}$ (or $a_{j} \in {\mathrm i} {\mathbb R}$) are pairwise different. Our method is based on the recently proposed stable iterative rational approximation algorithm in \cite{NST18}. For signal reconstruction we use a set of classical Fourier coefficients of $f$ with regard to a fixed interval $(0, P)$ with $P>0$. Even though all terms of $f$ may be non-$P$-periodic, our reconstruction method requires at most $2K+2$ Fourier coefficients $c_{n}(f)$ to recover all parameters of $f$. We show that in the case of exact data, the proposed iterative algorithm terminates after at most $K+1$ steps. The algorithm can also detect the number $K$ of terms of $f$, if $K$ is a priori unknown and $L>2K+2$ Fourier coefficients are available. Therefore our method provides a new stable alternative to the known numerical approaches for the recovery of exponential sums that are based on Prony's method. Keywords: sparse exponential sums, non-harmonic Fourier sums, reconstruction of sparse non-periodic signals, rational approximation, AAA algorithm, barycentric representation, Fourier coefficients