MC 5479
Annie Cuyt | University of Antwerp
Title
On the cross-fertilisation of Sparse interpolation and Exponential analysis
Abstract
The concepts of polynomial and trigonometric interpolation are well-known. The concepts of sparse interpolation (used in computer algebra) and exponential analysis (from digital signal processing) are generalizations thereof, where respectively the powers or the frequencies in the interpolant are not predefined to be 0, 1, 2, . . . Half of the data is then used to determine the appropriate powers or frequencies.
In this talk we discuss how sparse interpolation and exponential analysis can cross-fertilize and lead to new results. We thereby focus on the overarching inverse problem of identifying, from given values fk ∈ C, the nonlinear parameters φ1, . . . , φn ∈ C, the linear coefficients α1, . . . , αn ∈ C and the sparsity n ∈ N in the interpolation
∑_{j=1}^N αj exp(φj k∆) = fk, k = 0, . . . , 2n − 1, . . . ∆ ∈ R+.
In the literature, several cases of this expression are considered to be hard:
When some of the φj cluster, the identification and separation of these clustered φj becomes numerically ill-conditioned. We show how the problem may be reconditioned.
Retrieval of the correct value of n is difficult, and more so in case of clustered φj and noisy samples fk. Here, decimation of the data offers a way to obtain a reliable estimate of n automatically.
Such decimation allows one to divide and conquer the inverse problem statement. The smaller subproblems are largely independent and can be solved in parallel, leading to an improved complexity and efficiency.
At the same time, the sub-Nyquist1 Prony method proves to be robust with respect to outliers in the data. Making use of some exisiting approximation theory results, we can also validate the computation of the φj and αj
Avoiding the Nyquist constraint offers so-called superresolution, or the possibility to unearth higher frequency components in the samples.
All of the above can be generalized in several ways, to the use of more functions besides the exponential on the one hand, and to the solution of multidimensional inverse problems on the other.
Joint work with Wen-shin Lee, Stirling University, Scotland