A universal sampling method for reconstructing signals with simple Fourier transforms

Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. We are often interested in signals with "simple'' Fourier structure -- e.g., those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies -- i.e., bandlimited, sparse, and multiband signals, respectively. More broadly, any prior knowledge on a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct.

Authors

• Haim Avron
• Michael Kapralov
• Cameron Musco
• Christopher Musco
• Ameya Velingker
• Amir Zandieh

Keywords

• Leverage score sampling
• Numerical linear algebra
• Signal reconstruction