Search

We consider the problem of reconstructing a compactly supported function with singularities either from values of its Fourier transform available only in a bounded interval or from a limited number of its Fourier coefficients. Our results are based on several observations and algorithms in [G. Beylkin, L. Monzón, On approximation of functions by exponential sums, Appl. Comput. Harmon. Anal. 19 (1) (2005) 17–48]. We avoid both the Gibbs phenomenon and the use of windows or filtering by constructing approximations to the available Fourier data via a short sum of decaying exponentials. Using these exponentials, we extrapolate the Fourier data to the whole real line and, on taking the inverse Fourier transform, obtain an efficient rational representation in the spatial domain. An important feature of this rational representation is that the positions of its poles indicate location of singularities of the function. We consider these representations in the absence of noise and discuss the impact of adding white noise to the Fourier data. We also compare our results with those obtained by other techniques. As an example of application, we consider our approach in the context of the kernel polynomial method for estimating density of states (eigenvalues) of Hermitian operators. We briefly consider the related problem of approximation by rational functions and provide numerical examples using our approach.

We consider a simple approach for the fast evaluation of the Fourier transform of functions with singularities based on projecting such functions on a subspace of Multiresolution Analysis. We obtain an explicit approximation of the Fourier Transform of generalized functions and develop a fast algorithm based on its evaluation. In particular, we construct an algorithm for the Unequally Spaced Fast Fourier Transform and test its performance in one and two dimensions. The number of operations required by algorithms of this paper is O ( N · log N + N p · (− log ϵ)) in one dimension and O ( N 2 · log N + N p · (− log ϵ) 2 ) in two dimensions, where ϵ is the precision of computation, N is the number of computed frequencies and N p is the number of nodes. We also address the problem of using approximations of generalized functions for solving partial differential equation with singular coefficients or source terms.