Nearly optimal sparse fourier transform

Nearly optimal sparse fourier transform

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and An O(k log n log(n/k))-time randomized a...

Full description

Bibliographic Details
Main Authors: Hassanieh, Haitham, Indyk, Piotr, Katabi, Dina, Price, Eric C.
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Association for Computing Machinery (ACM) 2012
Online Access:http://hdl.handle.net/1721.1/72987
https://orcid.org/0000-0002-6689-8189
https://orcid.org/0000-0003-4854-4157
https://orcid.org/0000-0002-7983-9524

Internet

http://hdl.handle.net/1721.1/72987
https://orcid.org/0000-0002-6689-8189
https://orcid.org/0000-0003-4854-4157
https://orcid.org/0000-0002-7983-9524

Similar Items