Sparsity Order Estimation and its Application in Compressive Spectrum Sensing for Cognitive Radios

Compressive sampling techniques can effectively reduce the acquisition costs of high-dimensional signals by utilizing the fact that typical signals of interest are often sparse in a certain domain. For compressive samplers, the number of samples M_r needed to reconstruct a sparse signal is determined by the actual sparsity order S_nz of the signal, which can be much smaller than the signal dimension N. However, S_nz is often unknown or dynamically varying in practice, and the practical sampling rate has to be chosen conservatively according to an upper bound S_max of the actual sparsity order in lieu of S_nz, which can be unnecessarily high. To circumvent such wastage of the sampling resources, this paper introduces the concept of sparsity order estimation, which aims to accurately acquire S_nz prior to sparse signal recovery, by using a very small number of samples M_e less than M_r. A statistical learning methodology is used to quantify the gap between M_r and M_e in a closed form via data fitting, which offers useful design guideline for compressive samplers. It is shown that M_e ≥ 1.2S_nz log(N/S_nz + 2) + 3 for a broad range of sampling matrices. Capitalizing on this gap, this paper also develops a two-step compressive spectrum sensing algorithm for wideband cognitive radios as an illustrative application. The first step quickly estimates the actual sparsity order of the wide spectrum of interest using a small number of samples, and the second step adjusts the total number of collected samples according to the estimated signal sparsity order. By doing so, the overall sampling cost can be minimized adaptively, without degrading the sensing performance.