Name
Abstract | ||
|---|---|---|
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional √n × √n grid. Our algorithms are analyzed for the average case signals. For signals whose spectrum is exactly sparse, we present algorithms that use O(k) samples and run in O(k log k) time, where k is the expected sparsity of the signal. For signals whose spectrum is approximately sparse, we have an algorithm that uses O(k log n) samples and runs in O(k log2 n) time, for k = Θ(√n). All presented algorithms match the lower bounds on sample complexity for their respective signal models. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/Allerton.2013.6736670 | Communication, Control, and Computing |
Keywords | DocType | Volume |
compressed sensing,computational complexity,discrete Fourier transforms,signal sampling,discrete Fourier transform,sample complexity,sample optimal average case sparse Fourier transform,sample optimal sublinear time algorithms,signal sparsity,two dimensional grid | Journal | abs/1303.1209 |
ISSN | ISBN | Citations |
2474-0195 | 978-1-4799-3409-6 | 31 |
PageRank | References | Authors |
1.39 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Badih Ghazi | 1 | 88 | 15.07 |
| H. Hassanieh | 2 | 591 | 37.63 |
| Piotr Indyk | 3 | 10925 | 918.34 |
| Dina Katabi | 4 | 7819 | 453.05 |