  Recently, the statistical restricted isometry property (RIP) has been
formulated to analyze the performance of deterministic sampling matrices for
compressed sensing. In this paper, we propose the usage of orthogonal symmetric
Toeplitz matrices (OSTM) for compressed sensing and study their statistical RIP
by taking advantage of Stein's method. In particular, we derive the statistical
RIP performance bound in terms of the largest value of the sampling matrix and
the sparsity level of the input signal. Based on such connections, we show that
OSTM can satisfy the statistical RIP for an overwhelming majority of signals
with given sparsity level, if a Golay sequence used to generate the OSTM. Such
sensing matrices are deterministic, Toeplitz, and efficient to implement.
Simulation results show that OSTM can offer reconstruction performance similar
to that of random matrices.
