TY - GEN

T1 - Simple and practical algorithm for sparse fourier transform

AU - Hassanieh, Haitham

AU - Indyk, Piotr

AU - Katabi, Dina

AU - Price, Eric

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - We consider the sparse Fourier transform problem: given a complex vector ÷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 processing, notably Gaussian and Dolph-Chebyshev filters. Unlike the typical approach to this problem, our algorithm is not iterative. That is, instead of estimating "large" coefficients, subtracting them and recursing on the reminder, it identifies and estimates the k largest coefficients in "one shot", in a manner akin to sketching/streaming algorithms. 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.

AB - We consider the sparse Fourier transform problem: given a complex vector ÷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 processing, notably Gaussian and Dolph-Chebyshev filters. Unlike the typical approach to this problem, our algorithm is not iterative. That is, instead of estimating "large" coefficients, subtracting them and recursing on the reminder, it identifies and estimates the k largest coefficients in "one shot", in a manner akin to sketching/streaming algorithms. 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.

UR - http://www.scopus.com/inward/record.url?scp=84860189111&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860189111&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.93

DO - 10.1137/1.9781611973099.93

M3 - Conference contribution

AN - SCOPUS:84860189111

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1183

EP - 1194

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -