  In this paper, we discuss the development of a sublinear sparse Fourier
algorithm for high-dimensional data. In ``Adaptive Sublinear Time Fourier
Algorithm" by D. Lawlor, Y. Wang and A. Christlieb (2013), an efficient
algorithm with $\Theta(k\log k)$ average-case runtime and $\Theta(k)$
average-case sampling complexity for the one-dimensional sparse FFT was
developed for signals of bandwidth $N$, where $k$ is the number of significant
modes such that $k\ll N$.
  In this work we develop an efficient algorithm for sparse FFT for higher
dimensional signals, extending some of the ideas in the paper mentioned above.
Note a higher dimensional signal can always be unwrapped into a one dimensional
signal, but when the dimension gets large, unwrapping a higher dimensional
signal into a one dimensional array is far too expensive to be realistic. Our
approach here introduces two new concepts: ``partial unwrapping'' and
``tilting''. These two ideas allow us to efficiently compute the sparse FFT of
higher dimensional signals.

Numerical Analysis;Numerical Analysis