# Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions

arXiv: https://arxiv.org/abs/1303.1209 · HTML: https://mlsanity.com/paper/1303.1209/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2013.

## Built on by (most cited first, 1 of 1)

- [Efficient Algorithm for Sparse Fourier Transform of Generalized q-ary Functions](https://mlsanity.com/paper/2501.12365/) (2025)

## Abstract (arXiv)

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 for /average case/ signals. For signals whose spectrum is exactly sparse, our algorithms 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, our algorithm uses O(k log n) samples and runs in O(k log^2 n) time; the latter algorithm works for k=Theta(sqrt{n}). The number of samples used by our algorithms matches the known lower bounds for the respective signal models. By a known reduction, our algorithms give similar results for the one-dimensional sparse Discrete Fourier Transform when n is a power of a small composite number (e.g., n = 6^t).