Annie Cuyt

Gerlind Plonka, Yannick Riebe, Annie Cuyt

We present new short exponential sum approximations of length $N$ for $f_1(x)=\frac{1}{a+x}$ with $a>0$ on $[0, \infty)$ and for $f_2(x)= {\mathrm e}^{-x^2/2σ}$ with $σ>0$ on ${\mathbb R}$ with geometric error decay $ρ^{-2N}$ for user-defined $N \ge 2$ and $ρ>1$. The approximations are built over consecutive intervals $[b_j, \, b_{j+1}) \subset [0, \infty)$, $j \in {\mathbb N}_{0}$, with interval lengths that depend on $ρ$ and grow exponentially for $f_1$ and are equidistant for $f_2$. All parameters determining the exponential sum approximations on $[b_j, \, b_{j+1})$ are easily computed from the initial parameters on $[b_0, \, b_{1})$, ensuring numerical stability. Our method is based on Gauss-Laguerre and Gauss-Hermite quadrature, respectively, applied to suitable parametric integral representations of $f_1$ and $f_2$. This technique ensures consistent relative errors across all intervals. Using the obtained exponential sum approximations, we achieve highly accurate approximations of $\log(x)$ on $[1,\infty)$ and of the error function $\mathrm{erf}(x)$ with predictable geometric error decay. Numerical examples for $N=8$ and $N=10$ clearly illustrate the theoretical error estimates.

Annie Cuyt, Wen-shin Lee

The problem of multivariate exponential analysis or sparse interpolation has received a lot of attention, especially with respect to the number of samples required to solve it unambiguously. In this paper we show how to bring the number of samples down to the absolute minimum of $(d+1)n$ where $d$ is the dimension of the problem and $n$ is the number of exponential terms. To this end we present a fundamentally different approach for the multivariate problem statement. We combine a one-dimensional exponential analysis method such as ESPRIT, MUSIC, the matrix pencil or any Prony-like method, with some linear systems of equations because the multivariate exponents are inner products and thus linear expressions in the parameters.

Annie Cuyt, Wen-shin Lee

Sampling a signal below the Shannon-Nyquist rate causes aliasing, meaning different frequencies to become indistinguishable. It is also well-known that recovering spectral information from a signal using a parametric method can be ill-posed or ill-conditioned and therefore should be done with caution. We present an exponential analysis method to retrieve high-resolution information from coarse-scale measurements, using uniform downsampling. We exploit rather than avoid aliasing. While we loose the unicity of the solution by the downsampling, it allows to recondition the problem statement and increase the resolution. Our technique can be combined with different existing implementations of multi-exponential analysis (matrix pencil, MUSIC, ESPRIT, APM, generalized overdetermined eigenvalue solver, simultaneous QR factorization,...) and so is very versatile. It seems to be especially useful in the presence of clusters of frequencies that are difficult to distinguish from one another.

Matteo Briani, Annie Cuyt, Wen-shin Lee

The FFT algorithm that implements the discrete Fourier transform is considered one of the top ten algorithms of the $20$th century. Its main strengths are the low computational cost of $\mathcal{O}(n \log n$) and its stability. It is one of the most commonly used algorithms to analyze signals with a dense frequency representation. In recent years there has been an increasing interest in sparse signal representations and a need for algorithms that exploit such structure. We propose a new technique that combines the properties of the discrete Fourier transform with the sparsity of the signal. This is achieved by integrating ideas of Prony's method into Fourier's method. The resulting technique has the same frequency resolution as the original FFT algorithm but uses fewer samples and can achieve a lower computational cost. Moreover, the proposed algorithm is well suited for a parallel implementation.