Compressive Sensing with Sparse Measurement Matrices

This paper discusses compressive sensing with sparse measurement matrices. Such matrices have several attractive properties, like low computational complexity in both encoding and recovery, easy incremental updates to signals, and low storage requirement, etc. Existing algorithms for sparse signal recovery with sparse measurement matrices include matching pursuit, convex optimization and Bayesian framework. Matching pursuit has linear recovery complexity, and most of them can asymptotically guarantee the lower bound of sketch length (number of measurements). However, the empirical sketch length of some matching pursuit algorithms, like expander matching pursuit (EMP) and sparse matching pursuit (SMP), is always substantially higher than the lower bound. On the other hand, convex optimization and Bayesian framework has a much lower empirical sketch length than EMP and SMP, but also a higher recovery complexity that grows in a cubic-polynomial order with the length of source signals. In this paper, we propose a new compressive sensing technique with sparse measurement matrices, which contains a permutationbased multi-dimensional measurement matrix and an iterative recovery algorithm. The proposed measurement matrix is composed of several sub-matrices each consisting of a random permutation matrix and a matrix generated from direct sum of several equallength row vectors. The measurement symbols generated from the same permutation matrix are referred to as a dimension. The proposed iterative recovery algorithm fully utilizes the features of measurement symbols (due to the special structure of the measurement matrix used and the signal sparsity) to design simple local recovery in each iteration.