Nearly optimal Sparse FF
Halls department, Hall 3
Thursday, 29 December 2016
15:00 - 16:00
The problem of approximately computing the k dominant Fourier coefficients of a vector quickly and using few samples in time domain is known as the Sparse Fourier Transform (Sparse FFT) problem. A long line of work on Sparse FFT has resulted in algorithms with O(k logn log〖(n/k)〗) runtime and O(k logn) sample complexity [Hassanieh et al’STOC’12]. The mentioned result is non-adaptive, and is essentially the best possible under the sparsity assumption alone: It is known that even adaptive algorithms must use Ω((k logn)/loglogn ) samples [Hassanieh et al, STOC’12]. We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. The following are presented in [Hassanieh et al’STOC’12]: • An O(k logn)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and • An O(k logn log〖(n/k)〗)-time randomized algorithm for general input signals. Both algorithms achieve o(n logn) time, and thus improve over the Fast Fourier Transform, for any k=o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k=n^(Ω(1)).
Amir Zandieh is a PhD student at EPFL. He works on randomized approximation algorithms and is advised by prof. Michael Kapralov. His research interests are on Sparse recovery as well as sketching and Fourier sampling.