27 citations · 57 across the 6 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2013★ 11 cited
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk +3
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid. Our algorithms are analyzed f…
cs.DS2012★ 27 cited
Nearly Optimal Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi +1
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…