Sparse high-dimensional FFT based on rank-1 lattice sampling

In this paper, we suggest approximate algorithms for the reconstruction of sparse high-dimensional trigonometric polynomials, where the support in frequency domain is unknown. Based on ideas of constructing rank-1 lattices component-by-component, we adaptively construct the index set of frequencies belonging to the non-zero Fourier coefficients in a dimension incremental way. When we restrict the search space in frequency domain to a full grid [−N,N]d∩Zd[−N,N]d∩Zd of refinement N∈NN∈N and assume that the cardinality of the support of the trigonometric polynomial in frequency domain is bounded by the sparsity s∈Ns∈N, our method requires O(ds2N) samples and O(ds3+ds2Nlog⁡(sN)) arithmetic operations in the case N≲s≲Nd. Moreover, we discuss possibilities to reduce the number of samples and arithmetic operations by applying methods from compressed sensing and a version of Prony's method. For the latter, the number of samples is reduced to O(ds+dN) and the number of arithmetic operations is O(ds3). Various numerical examples demonstrate the efficiency of the suggested method.