Lower Bounds on the Number of Measurements of Sparse Random Matrices

Sparse recovery problem in the theory of compressed sensing is to recover a high-dimensional signal from its low-dimensional projection, and a dense random matrix is usually used as the measurement matrix to solve this problem. While some sparse random matrices as the measurement matrices can also achieve this goal. Sparse random matrices have several attractive properties, like low computational complexity in both encoding and recovery, easy incremental updates, and low storage requirement. Based on the theory of compressed sensing, this paper investigates sparse random matrices with fixed column sparsity or fixed row sparsity and general sparse random matrices respectively, and when these sparse random matrices satisfy the restricted isometry property, the lower bound conditions that the number of measurements should satisfy are deduced, and the performance of three matrices is analysed. Binary sparse random matrices are taken as a special example to do simulation experiments. Numerical results show that, the lower bounds on the number of measurements given by this paper are tight, and the feasibility and practicability of sparse random matrices with fixed column sparsity or fixed row sparsity as the measurement matrices are verified.