  The reconstruction of high-dimensional sparse signals is a challenging task
in a wide range of applications. In order to deal with high-dimensional
problems, efficient sparse fast Fourier transform algorithms are essential
tools. The second and third authors have recently proposed a
dimension-incremental approach, which only scales almost linear in the number
of required sampling values and almost quadratic in the arithmetic complexity
with respect to the spatial dimension $d$. Using reconstructing rank-1 lattices
as sampling scheme, the method showed reliable reconstruction results in
numerical tests but suffers from relatively large numbers of samples and
arithmetic operations. Combining the preferable properties of reconstructing
rank-1 lattices with small sample and arithmetic complexities, the first author
developed the concept of multiple rank-1 lattices. In this paper, both concepts
- dimension-incremental reconstruction and multiple rank-1 lattices - are
coupled, which yields a distinctly improved high-dimensional sparse fast
Fourier transform. Moreover, the resulting algorithm is analyzed in detail with
respect to success probability, number of required samples, and arithmetic
complexity. In comparison to single rank-1 lattices, the utilization of
multiple rank-1 lattices results in a reduction in the complexities by an
almost linear factor with respect to the sparsity. Various numerical tests
confirm the theoretical results, the high performance, and the reliability of
the proposed method.
