High-dimensional sparse Fourier algorithms

Abstract

In this paper, we discuss the development of a sublinear sparse Fourier algorithm for high-dimensional data. In 11Adaptive Sublinear Time Fourier Algorithm” by Lawlor et al. (Adv. Adapt. Data Anal.5(01):1350003, 2013), an efficient algorithm with Θ (klog k) average-case runtime and Θ(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 ≪ N. In this work we develop an efficient algorithm for sparse FFT for higher dimensional signals, extending some of the ideas in Lawlor et al. (Adv. Adapt. Data Anal.5(01):1350003, 2013). 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.