Simple and practical algorithm for sparse fourier transform
We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coe fficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, a...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73474 https://orcid.org/0000-0002-6689-8189 https://orcid.org/0000-0003-4854-4157 https://orcid.org/0000-0002-7983-9524 |
| Summary: | We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coe fficients 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" coeffi cients, subtracting them and recursing on the reminder, it identifi es and estimates the k largest coeffi cients 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. |
|---|