Abstract: Reconstructing signals from a small number of potentially noisy samples is a fundamental problem in signal processing. 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 the sample complexity of learning a continuous signal from a given class is characterized by the statistical dimension of the allowed power spectrum of that class. Surprisingly, we also show that, up to logarithmic factors, a universal, randomized sampling strategy can achieve this optimal complexity for any class of Fourier constrained signals. For bandlimited and sparse signals, our method matches the state-of-the-art (based on prolate spheroidal wave function regression and sparse Fourier transform/compressed sensing methods respectively). At the same time, it gives the first computationally and sample efficient solution to a broad range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension.

Our work is based on a connection between randomized numerical 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 are hopeful that these extensions are just the first step in tackling a broad range of continuous time signal processing problems using tools from randomized numerical linear algebra.