Exact Reconstruction of Sparse Non-Harmonic Signals from Fourier Coefficients

Abstract

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

28 pages, 2 figures