Abstract
Reconstructing signals based on 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 transforms -- e.g. those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies (bandlimited, sparse, and multiband signals, respectively). We generally find that "simpler" signals require fewer samples to learn. In this talk, I will introduce a general framework for learning continuous signals that formalizes this tradeoff between sample complexity and simplicity. Our framework is based on a connection between the signal reconstruction problem, low-rank matrix approximation, and randomized numerical linear algebra. In particular, we use tools based on leverage score sampling, and show that the number of samples required for learning a signal depends on a natural statistical dimension parameter related to these scores. Using this framework, I will also present a simple and efficient algorithm for signal reconstruction. For well-studied classes of signals (bandlimited, sparse, and multiband) our algorithm essentially matches the runtime and sample complexity of state-of-the-art methods. At the same time, it extends to a much broader class of ``simple'' signals. The main computation cost of our method is a black-box call to any existing algorithm for kernel ridge regression.