# (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2019.

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

- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)

## Abstract (arXiv)

In this paper, we consider the extensively studied problem of computing a k-sparse approximation to the d-dimensional Fourier transform of a length n signal. Our algorithm uses O(k log k log n) samples, is dimension-free, operates for any universe size, and achieves the strongest ℓ_∞/ℓ2 guarantee, while running in a time comparable to the Fast Fourier Transform. In contrast to previous algorithms which proceed either via the Restricted Isometry Property or via filter functions, our approach offers a fresh perspective to the sparse Fourier Transform problem.