The Discrete Fourier Transform (DFT) plays a crucial role in signal processing and scientific computing. The most famous algorithm for computing the DFT is the Fast Fourier Transform (FFT), which has runtime O(N log N) for an input vector with length N. However, with the increasing size of data set, the FFT is no longer fast enough and often becomes the major computational bottleneck in many applications. The Sparse Fourier Transform (SFT) tries to solve this problem by finding the best s−term Fourier representation using only a subset of the input data, in time sub-linear in the data set size O(poly(s;log N)). Some of the existing SFT algorithms are capable of working with equally spaced samples, while others just assume that the algorithms can sample anywhere they want, which is an unrealistic assumption in many real-world applications. In this thesis, we propose a generic method of transforming any noise robust SFT algorithm into a sublinear-time sparse DFT algorithm which rapidly approximates Ff from a given input vector f 2 CN, where F is the DFT matrix. Our approach is based on filter function and fast discrete convolution. We prove that with an appropriate filter function g (periodic Gaussian function in this thesis), one can always approximate the value of the convolution function g ∗ f at the desired point rapidly and accurately even when f is a high oscillating function. We then construct several new sublinear-time sparse DFT algorithms from existing sparse Fourier algorithms which utilize unequally spaced function samples. Besides giving the theoretical runtime and error guarantee, we also show empirically that the best of these new discrete SFT algorithms outperforms both FFTW and sFFT2.0 in the sense of runtime and robustness when the vector length N is large. At the end of the thesis, we present a deterministic sparse Fourier transform algorithm which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. We show empirically that this structured SFT algorithm outperforms standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions.
Read
