Arbitrary Block-Sparse Signal Reconstruction Based on Incomplete Single Measurement Vector

摘要

Within the compressive sensing framework, reconstruction algorithms of block-sparse signal (BSS) often have special requirements on sparsity patterns. As a result, only some particular BSSs can be reconstructed. In this paper, we present a new universal greedy iteration algorithm, named block-matching pursuit (BMP), for BSS with an arbitrary sparsity pattern. The BMP can reconstruct the target signal without prior information of the signal's sparsity pattern and achieves an outstanding reconstruction probability. In each iteration, the BMP first estimates a part of support set of the signal by a correlation test. Based on the estimated support and the property of nonzero blocks, coordinates of all possible nonzero entries can be obtained to form a candidate list. Then some coordinates in the list, which are deemed sufficiently reliable by a final test, are added to the current estimated support set. When iteration ends, the true sparsity level, namely true support set, can be exactly calculated by searching a support set with the smallest cardinality; once the true set is derived, the target signal can be reconstructed. Theoretical analysis indicates that BMP can reconstruct the target signal as long as the sampling matrix meets a certain condition. Simulation results show that the reconstruction performance of BMP is better than that of other greedy algorithms. In particular, if the signal with high sparsity level contains a few blocks, BMP can still reconstruct it with a high probability.