We present a new deterministic algorithm for the sparse Fourier transform problem, in which we seek to identify k << N significant Fourier coefficients from a signal of bandwidth N. Previous deterministic algorithms exhibit quadratic runtime scaling in k, while our algorithm scales linearly with k in the average case. Underlying our algorithm are a few simple observations relating the Fourier coefficients of time-shifted samples to unshifted samples of the input function. This allows us to detect when aliasing between two or more frequencies has occurred, as well as to determine the value of unaliased frequencies. We also show that the small time shifts required for our algorithm can be implemented using two much larger shifts, an important point for applications where the sampling rate is limited by hardware capacity. Empirically our algorithm is orders of magnitude faster than competing algorithms.We study the effect of noise on the performance of our algorithm, and derive a relationship between its magnitude and the rate at which the signal is sampled. This in turn is used to devise modified versions of our basic algorithm that are robust to noise, although with higher runtime and sampling requirements than in the noiseless case. The first of these is a minor change, and exhibits poor performance relative to the noise level. To remedy this we propose a multi-scale algorithm that allows for error correction in the frequency estimates in an iterative fashion. It is shown empirically that this multi-scale algorithm is robust to noise even with coarse sampling rates.Finally, we discuss the application of our algorithms to the multi-dimensional setting. A straightforward extension, while simple to describe and implement, exhibits exponential scaling with the dimension. A second extension is then proposed that uses number-theoretic techniques to reduce the multi-dimensional problem to the one-dimensional case, which can then be solved efficiently with the algorithm proposed in chapter two. An empirical evaluation shows that this second method significantly outperforms highly optimized FFT implementations in two dimensions.
Read
