Abstract
Efficient spectrum sensing is an important problem given the large and increasing demand for wireless spectrum and the need to protect incumbent users. We can more efficiently use large swaths of underutilized spectrum by designing spectrum sensors that can quickly, and power-efficiently, find and opportunistically communicate over unused (or underutilized) pieces of spectrum, such as television bands. In this paper, we concentrate on a particular sensing architecture, the Random Demodulator (RD), and look at two aspects of the problem. First, we offer fundamental limits on how efficiently any algorithm can perform the sensing operation with the RD. Second, we analyze a very simple, low-complexity algorithm called one-step thresholding that has been shown to work near-optimally for certain measurement classes in a low SNR setting or when the non-zero input coefficients are nearly equal. We rigorously establish that the RD architecture is well-suited for near-optimal recovery of the locations of the non-zero frequency coefficients in similar settings using one-step thresholding and perform numerical experiments to offer some confirmation of our results.