The semi-tensor product (STP) approach is an effective way to reduce the storage space of a random measurement matrix for compressed sensing (CS)

in which the dimensions of the random measurement matrix can be reduced to a quarter (or a sixteenth

or even less) of the dimensions used for conventional CS. A smooth l-norm minimization algorithm for CS with the STP is proposed to improve reconstruction performance. We generate a random measurement matrix

in which the matrix dimensions are reduced to 1/4

1/16

1/64

or 1/256 of the dimensions used for conventional CS. We then estimate the solutions of the sparse vector with the smooth l-norm minimization algorithm. Numerical experiments are conducted using column sparse signals and images of various sizes. The probability of exact reconstruction

rate of convergence

and peak signal-to-noise ratio of the reconstruction solutions are compared with the random matrices with different dimensions. Numerical simulation results show that the proposed algorithm can reduce the storage space of the random measurement matrix to at least 1/4 while maintaining reconstruction performance. The proposed algorithm can reduce the dimensions of the random measurement matrix to a great extent than the l-norm (0 < <1) minimization algorithm

thereby maintaining the reconstruction quality.