February Fourier Talks 2019

In many applications, most of the Fourier coefficients of input signals are "small" or equal to zero. That is, the output of the transform is (approximately) sparse. For such signals, it is known that the Fast Fourier Transform algorithm is not optimal, and that faster algorithms exist. Those algorithms are collectively known as Sparse Fourier Transforms.

In this talk, I will outline a class of efficient Sparse Fourier Transform algorithms. The most efficient of them has the running time of O(k log n), where k is the number of non-zero Fourier coefficients of the signal. I will also describe some of their applications and list a few outstanding open problems, of both theoretical and practical nature.