A Universal Sampling Method for Reconstructing Signals with Simple
  Fourier Transforms
  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.
