(Nearly) sample-optimal sparse fourier transform
We consider the problem of computing a k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using O(k log n(log log n)[superscript O(1)]) signal samples in time O(k log[superscript 2] n(log...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114162 https://orcid.org/0000-0002-7983-9524 |