Computational Complexity Reduction in Nonuniform Compressed Sensing by Multi-Coset Emulation

Abstract Single-channel Nonuniform Sampling (SNS) is a Compressed Sensing (CS) approach that allows sub-Nyquist sampling of frequency sparse signals. The relatively simple architecture, comprising one wide-band sampling channel, makes it an attractive solution for applications such as signal analyzers and telecommunications. However, a high computational cost of the \{SNS\} signal reconstruction is an obstacle for real-time applications. This paper proposes to emulate Multi-Coset Sampling (MCS) in \{SNS\} acquisition as a means to decrease the computational costs. Such an emulation introduces performance–complexity tradeoffs due to the difference of the \{SNS\} and \{MCS\} models. We investigate these tradeoffs with numerical simulations and theoretical assessments of the reconstruction complexity in multi-band signal scenarios. These scenarios include different numbers, different widths and positions of the frequency bands and different levels of noise in the signals. For the \{SNS\} reconstruction, we consider the accelerated iterative hard thresholding algorithm; for the \{MCS\} reconstruction, the multiple signal classification and focal underdetermined system solver algorithms are used. The proposed emulation reduces the computational complexity up to several orders of magnitude. For one of the scenarios, the reconstruction quality slightly decreases. For the other scenarios, the reconstruction quality is either preserved or improved.