Fast discrete algorithms for sparse Fourier expansions of high dimensional functions

We develop a fast discrete algorithm for computing the sparse Fourier expansion of a function of dd dimension. For this purpose, we introduce a sparse multiscale Lagrange interpolation method for the function. Using this interpolation method, we then design a quadrature scheme for evaluating the Fourier coefficients of the sparse Fourier expansion. This leads to a fast discrete algorithm for computing the sparse Fourier expansion. We prove that this method gives the optimal approximation order O(n−s)O(n−s) for the sparse Fourier expansion, where s>0s>0 is the order of the Sobolev regularity of the function to be approximated and where nn is the order of the univariate trigonometric polynomial used to construct the sparse multivariate approximation, and requires only O(nlog2d−1n)O(nlog2d−1n) number of multiplications to compute all of its Fourier coefficients. We present several numerical examples with d=2,3d=2,3 and 44 that confirm the theoretical estimates of approximation order and computational complexity and compare the numerical performance of the proposed method with that of a well-known existing algorithm. We also have a numerical example for d=8d=8 to test the efficiency of the propose algorithm for functions of a higher dimension.