Minimum-Rate Spectrum-Blind Sampling Based on Sparse-Graph Codes

Abstract

We study the problem of spectrum-blind sampling, that is, sampling signals with sparse spectra whose frequency support is unknown. The minimum sampling rate for this class of signals has been established as twice the measure of its frequency support; however, constructive schemes that achieve this minimum rate are not known to exist, to the best of our knowledge. We propose a novel constructive sampling framework by leveraging tools from modern coding theory, which has been largely untapped in the field of sampling. We make interesting connections between the problem of spectrum-blind sampling, and that of designing erasure-correcting codes based on sparse graphs. Our key idea is to cleverly exploit the aliasing artifacts induced by subsampling, introducing linear mixing of spectral components in the form of parity constraints for sparse-graph codes. We achieve this by subsampling the input signal after filtering it using a carefully designed 'sparse-graph coded filter bank', where the pass-band patterns are designed to match the parity-check constraints of a sparse-graph code. We show that the signal reconstruction under this scheme is equivalent to the fast 'peeling' decoding of sparse-graph codes. We further show that the achievable sampling rate is determined by the rate of the codes used in the filter bank. As a result, based on insights derived from the design of capacity-achieving sparse-graph codes, we can simultaneously approach the minimum sampling rate for spectrum-blind sampling and low computational complexity based on fast peeling-based decoding with operations per unit of time scaling linearly with the sampling rate.