Restricted Isometry Property Analysis for Sparse Random Matrices

Sparse random matrices have attractive properties, such as low storage requirement, low computational complexity in both encoding and recovery, easy incremental updates, and they show great advantages in distributed applications. To make sure sparse random matrices can be used as the measurement matrix, the Restricted Isometry Property (RIP) of such matrices is proved in this paper. Firstly, it is shown that the measurement matrix satisfies RIP is equivalent to the Gram matrix of its submatrix has all of eigenvalues around 1; then it is proved that sparse random matrices satisfy RIP with high probability provided the numbers of measurements satisfy certain conditions. Simulation results show that sparse random matrices can guarantee accurate reconstruction of original signal, while greatly reduce the time of measuring and reconstruction.