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 |
| _version_ | 1826205046683992064 |
|---|---|
| author | Hassanieh, Haitham Indyk, Piotr Katabi, Dina Price, Eric C. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Hassanieh, Haitham Indyk, Piotr Katabi, Dina Price, Eric C. |
| author_sort | Hassanieh, Haitham |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:05:54Z |
| format | Article |
| id | mit-1721.1/73474 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:05:54Z |
| publishDate | 2012 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/734742022-10-01T13:01:02Z Simple and practical algorithm for sparse fourier transform Hassanieh, Haitham Indyk, Piotr Katabi, Dina Price, Eric C. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Hassanieh, Haitham Indyk, Piotr Katabi, Dina Price, Eric C. 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. 2012-09-28T15:51:05Z 2012-09-28T15:51:05Z 2012-01 Article http://purl.org/eprint/type/ConferencePaper 2160-1445 1557-9468 1071-9040 http://hdl.handle.net/1721.1/73474 Hassanieh, Haitham et al. "Simple and practical algorithm for sparse fourier transform." Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, January 17-19, 2012, Kyoto, Japan. © 2012 by the Society for Industrial and Applied Mathematics. https://orcid.org/0000-0002-6689-8189 https://orcid.org/0000-0003-4854-4157 https://orcid.org/0000-0002-7983-9524 en_US http://siam.omnibooksonline.com/2012SODA/index.html Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Hassanieh, Haitham Indyk, Piotr Katabi, Dina Price, Eric C. Simple and practical algorithm for sparse fourier transform |
| title | Simple and practical algorithm for sparse fourier transform |
| title_full | Simple and practical algorithm for sparse fourier transform |
| title_fullStr | Simple and practical algorithm for sparse fourier transform |
| title_full_unstemmed | Simple and practical algorithm for sparse fourier transform |
| title_short | Simple and practical algorithm for sparse fourier transform |
| title_sort | simple and practical algorithm for sparse fourier transform |
| url | 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 |
| work_keys_str_mv | AT hassaniehhaitham simpleandpracticalalgorithmforsparsefouriertransform AT indykpiotr simpleandpracticalalgorithmforsparsefouriertransform AT katabidina simpleandpracticalalgorithmforsparsefouriertransform AT priceericc simpleandpracticalalgorithmforsparsefouriertransform |