# A Robust Sparse Fourier Transform in the Continuous Setting

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

## Key facts

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

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

- [Diversified Recommendations for Agents with Adaptive Preferences](https://mlsanity.com/paper/2210.07773/) (2022)
- [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)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)

## Abstract (arXiv)

In recent years, a number of works have studied methods for computing the Fourier transform in sublinear time if the output is sparse. Most of these have focused on the discrete setting, even though in many applications the input signal is continuous and naive discretization significantly worsens the sparsity level. We present an algorithm for robustly computing sparse Fourier transforms in the continuous setting. Let x(t) = x^*(t) + g(t), where x^* has a k-sparse Fourier transform and g is an arbitrary noise term. Given sample access to x(t) for some duration T, we show how to find a k-Fourier-sparse reconstruction x'(t) with frac1Tint0T |x'(t) - x(t) |2 d t lesssim frac1Tint0T | g(t)|2 dt. The sample complexity is linear in k and logarithmic in the signal-to-noise ratio and the frequency resolution. Previous results with similar sample complexities could not tolerate an infinitesimal amount of i.i.d. Gaussian noise, and even algorithms with higher sample complexities increased the noise by a polynomial factor. We also give new results for how precisely the individual frequencies of x^* can be recovered.