TY - GEN
T1 - A universal sampling method for reconstructing signals with simple Fourier transforms
AU - Avron, Haim
AU - Kapralov, Michael
AU - Musco, Cameron
AU - Musco, Christopher
AU - Velingker, Ameya
AU - Zandieh, Amir
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2019/6/23
Y1 - 2019/6/23
N2 - 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. 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. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to log factors, a universal nonuniform sampling strategy can achieve this optimal complexity for any class of signals. We present an efficient and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art, while providing the the first computationally and sample efficient solution to a broader range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals 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 the signal reconstruction problem. We believe these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.
AB - 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. 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. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to log factors, a universal nonuniform sampling strategy can achieve this optimal complexity for any class of signals. We present an efficient and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art, while providing the the first computationally and sample efficient solution to a broader range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals 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 the signal reconstruction problem. We believe these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.
KW - Leverage score sampling
KW - Numerical linear algebra
KW - Signal reconstruction
UR - http://www.scopus.com/inward/record.url?scp=85068798658&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068798658&partnerID=8YFLogxK
U2 - 10.1145/3313276.3316363
DO - 10.1145/3313276.3316363
M3 - Conference contribution
AN - SCOPUS:85068798658
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1051
EP - 1063
BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
A2 - Charikar, Moses
A2 - Cohen, Edith
PB - Association for Computing Machinery
T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
Y2 - 23 June 2019 through 26 June 2019
ER -