# A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2018.

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

- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time](https://mlsanity.com/paper/2202.04515/) (2022)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [Robust Model Selection and Nearly-Proper Learning for GMMs](https://mlsanity.com/paper/2106.02774/) (2021)
- [Signal reconstruction using determinantal sampling](https://mlsanity.com/paper/2310.09437/) (2023)
- [Near Optimal Reconstruction of Spherical Harmonic Expansions](https://mlsanity.com/paper/2202.12995/) (2022)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)
- [Active Learning for Conditional Generative Compressed Sensing](https://mlsanity.com/paper/2605.05435/) (2026)

## Abstract (arXiv)

Reconstructing continuous signals from a small number of discrete samples is a fundamental problem across science and engineering. In practice, we are often interested in signals with 'simple' Fourier structure, such as bandlimited, multiband, and Fourier sparse signals. More broadly, any prior knowledge about a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct. We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the *statistical dimension* of the allowed power spectrum of that class. Further, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to logarithmic factors, a universal non-uniform sampling strategy can achieve this optimal complexity for *any class of signals*. We present a simple and efficient algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art. At the same time, it gives the first computationally and sample efficient solution to a broad range of problems, including multiband signal reconstruction and kriging and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and signal reconstruction with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in signal reconstruction. We believe that these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.