sFFT: Sparse Fast Fourier TransformAlgorithm Evaluation Publications People
IntroductionWe consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal pro- cessing, notably Gaussian and Dolph-Chebyshev filters. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice. Algorithm
Evaluation
PublicationsSimple and Practical Algorithm for Sparse Fourier TransformHaitham Hassanieh, Piotr Indyk ,Dina Katabi, and Eric Price. PDF SODA, January 2012. Nearly Optimal Sparse Fourier Transform Haitham Hassanieh, Piotr Indyk ,Dina Katabi, and Eric Price. PDF STOC 2012 (accepted) People :
|
