Fast Band-Limited Sparse Signal Reconstruction Algorithms for Big Data Processing

With the increasing size of datasets in wideband spectrum sensing, high-resolution radar imaging and high-definition multimedia, real-time computation, and sample storage have become a big challenge. In the above-mentioned applications, signals are usually band limited and sparse, which has block sparse features in the frequency domain. In this article, we consider the block sparse feature and propose fast band-limited sparse signal reconstruction algorithms for big data processing. We first give the optimization strategy to reduce the complexity of reconstruction and propose the optimization theory for band-limited sparse signals with rigorous mathematical proofs. Then, two versions of band-limited sparse Fourier transform (BLSFT), i.e., BLSFT V1 and BLSFT V2, are designed based on the optimization theory. Both of the proposed algorithms are universal algorithms with sublinear computational and sample complexity. Numerical simulations confirm that BLSFT is superior to state-of-the-art algorithms in complexity and robustness. Finally, we discuss the application of BLSFT in real-time spectrum sensing of frequency hopping signals and demonstrate its feasibility via real-world experiments.