# Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2013.

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

- [Learning to Understand: Identifying Interactions via the M"obius Transform](https://mlsanity.com/paper/2402.02631/) (2024)
- [SPEX: Scaling Feature Interaction Explanations for LLMs](https://mlsanity.com/paper/2502.13870/) (2025)
- [Adaptive Sparse M"obius Transforms for Learning Polynomials](https://mlsanity.com/paper/2602.06246/) (2026)

## Abstract (arXiv)

Given an n-length input signal mbfx, it is well known that its Discrete Fourier Transform (DFT), mbfX, can be computed in O(n log n) complexity using a Fast Fourier Transform (FFT). If the spectrum mbfX is exactly k-sparse (where k<<n), can we do better? We show that asymptotically in k and n, when k is sub-linear in n (precisely, k propto nδ where 0 < δ <1), and the support of the non-zero DFT coefficients is uniformly random, we can exploit this sparsity in two fundamental ways (i) bf sample complexity: we need only M=rk deterministically chosen samples of the input signal mbfx (where r < 4 when 0 < δ < 0.99); and (ii) bf computational complexity: we can reliably compute the DFT mbfX using O(k log k) operations, where the constants in the big Oh are small and are related to the constants involved in computing a small number of DFTs of length approximately equal to the sparsity parameter k. Our algorithm succeeds with high probability, with the probability of failure vanishing to zero asymptotically in the number of samples acquired, M.