Stefan Kunis

Martin Ehler, Stefan Kunis, Thomas Peter et al.

The matrix pencil method is an eigenvalue based approach for the parameter identification of sparse exponential sums. We derive a reconstruction algorithm for multivariate exponential sums that is based on simultaneous diagonalization. Randomization is used and quantified to reduce the simultaneous diagonalization to the eigendecomposition of a single random matrix. To verify feasibility, the algorithm is applied to synthetic and experimental fluorescence microscopy data.

Stefan Kunis, H. Michael Möller, Ulrich von der Ohe

Eigenvalue analysis based methods are well suited for the reconstruction of finitely supported measures from their moments up to a certain degree. We give a precise description when Prony's method succeeds in terms of an interpolation condition. In particular, this allows for the unique reconstruction of a measure from its trigonometric moments whenever its support is separated and also for the reconstruction of a measure on the unit sphere from its moments with respect to spherical harmonics. Both results hold in arbitrary dimensions and also yield a certificate for popular semidefinite relaxations of these reconstruction problems.

Stefan Kunis, Ines Melzer

Recently, the butterfly approximation scheme and hierarchical approximations have been proposed for the efficient computation of integral transforms with oscillatory and with asymptotically smooth kernels. Combining both approaches, we propose a certain fast Fourier-Laplace transform, which in particular allows for the fast evaluation of polynomials at nodes in the complex unit disk. All theoretical results are illustrated by numerical experiments.

Stefan Kunis, H. Michael Möller, Thomas Peter et al.

The parameter reconstruction problem in a sum of Dirac measures from its low frequency trigonometric moments is well understood in the univariate case and has a sharp transition of identifiability with respect to the ratio of the separation distance of the parameters and the order of moments. Towards a similar statement in the multivariate case, we present an Ingham inequality which improves the previously best known dimension-dependent constant from square-root growth to a logarithmic one. Secondly, we refine an argument that an Ingham inequality implies identifiability in multivariate Prony methods to the case of commonly used max-degree by a short linear algebra argument, closely related to a flat extension principle and the stagnation of a generalized Hilbert function.

Stefan Kunis, Thomas Peter, Tim Roemer et al.

Prony's method is a prototypical eigenvalue analysis based method for the reconstruction of a finitely supported complex measure on the unit circle from its moments up to a certain degree. In this note, we give a generalization of this method to the multivariate case and prove simple conditions under which the problem admits a unique solution. Provided the order of the moments is bounded from below by the number of points on which the measure is supported as well as by a small constant divided by the separation distance of these points, stable reconstruction is guaranteed. In its simplest form, the reconstruction method consists of setting up a certain multilevel Toeplitz matrix of the moments, compute a basis of its kernel, and compute by some method of choice the set of common roots of the multivariate polynomials whose coefficients are given in the second step. All theoretical results are illustrated by numerical experiments.

Stefan Kunis, Holger Rauhut

We investigate the problem of reconstructing sparse multivariate trigonometric polynomials from few randomly taken samples by Basis Pursuit and greedy algorithms such as Orthogonal Matching Pursuit (OMP) and Thresholding. While recovery by Basis Pursuit has recently been studied by several authors, we provide theoretical results on the success probability of reconstruction via Thresholding and OMP for both a continuous and a discrete probability model for the sampling points. We present numerical experiments, which indicate that usually Basis Pursuit is significantly slower than greedy algorithms, while the recovery rates are very similar.

Stefan Kunis, Daniel Potts

A fast and reliable algorithm for the optimal interpolation of scattered data on the torus by multivariate trigonometric polynomials is presented. The algorithm is based on a variant of the conjugate gradient method in combination with the fast Fourier transforms for nonequispaced nodes. The main result is that under mild assumptions the total complexity for solving the interpolation problem at M arbitrary nodes is of order O(M logM). This result is obtained by the use of localised trigonometric kernels where the localisation is chosen in accordance to the spatial dimension d. Numerical examples show the efficiency of the new algorithm.