  In this paper a sublinear time algorithm is presented for the reconstruction
of functions that can be represented by just few out of a potentially large
candidate set of Fourier basis functions in high spatial dimensions, a
so-called high-dimensional sparse fast Fourier transform. In contrast to many
other such algorithms, our method works for arbitrary candidate sets and does
not make additional structural assumptions on the candidate set. Our transform
significantly improves upon the other approaches available for such a general
framework in terms of the scaling of the sample complexity. Our algorithm is
based on sampling the function along multiple rank-1 lattices with random
generators.
  Combined with a dimension-incremental approach, our method yields a sparse
Fourier transform whose computational complexity only grows mildly in the
dimension and can hence be efficiently computed even in high dimensions. Our
theoretical analysis establishes that any Fourier $s$-sparse function can be
accurately reconstructed with high probability. This guarantee is complemented
by several numerical tests demonstrating the high efficiency and versatile
applicability for the exactly sparse case and also for the compressible case.
