On Sparse Fourier Transform

Abstract: The Discrete Fourier Transform (DFT) is one of the most useful and powerful transformations in science and engineering. It is also a wonderfully efficient algorithm. Interestingly, when the data is sparse we can do better. We discuss algorithms for the sparse Fourier transform problem, in which we seek to identify $k \leq N$ significant Fourier coefficients from a signal of bandwidth $N$. We also present a multi-scale algorithm for noisy signals which proves to be extremely robust and efficient. This multi-scale algorithm is based on the beta-expansion scheme for robust A/D conversion. We also present the first efficient algorithm for ultra-high dimensions signals.