Deterministic compressed-sensing matrices: Where Toeplitz meets Golay

Recently, the statistical restricted isometry property (STRIP) has been formulated to analyze the performance of deterministic sampling matrices for compressed sensing. In this paper, a class of deterministic matrices which satisfy STRIP with overwhelming probability are proposed, by taking advantage of concentration inequalities using Stein's method. These matrices, called orthogonal symmetric Toeplitz matrices (OSTM), guarantee successful recovery of all but an exponentially small fraction of K-sparse signals. Such matrices are deterministic, Toeplitz, and easy to generate. We derive the STRIP performance bound by exploiting the specific properties of OSTM, and obtain the near-optimal bound by setting the underlying sign sequence of OSTM as the Golay sequence. Simulation results show that these deterministic sensing matrices can offer reconstruction performance similar to that of random matrices.