Fast discrete algorithms for sparse Fourier expansions of high dimensional functions (Q2655801)

The authors develop a fast algorithm for computing the sparse Fourier expansion of a \(d\)-variate function \(f\) with Sobolev regularity of order \(s>0\). In a sparse Fourier expansion, the frequency vectors of the \(d\)-variate exponentials form a so-called hyperbolic cross. Using a sparse multiscale Lagrange interpolation method, the authors design a quadrature scheme for evaluating the corresponding Fourier coefficients of \(f\). Further they show that this method gives optimal approximation order \({\mathcal O}(n^{-s})\) for the sparse Fourier expansion of \(f\), where \(n\) is the order of the univariate trigonometric polynomial used to construct the sparse Fourier expansion, and requires \({\mathcal O}(n\,(\log\, n)^{2d-1})\) multiplications to compute all the needed Fourier coefficients of \(f\). Numerical examples are presented for \(d\in \{2,\,3,\,4,\,8\}\).