  Compressed sensing seeks to recover a sparse vector from a small number of
linear and non-adaptive measurements. While most work so far focuses on
Gaussian or Bernoulli random measurements we investigate the use of partial
random circulant and Toeplitz matrices in connection with recovery by
$\ell_1$-minization. In contrast to recent work in this direction we allow the
use of an arbitrary subset of rows of a circulant and Toeplitz matrix. Our
recovery result predicts that the necessary number of measurements to ensure
sparse reconstruction by $\ell_1$-minimization with random partial circulant or
Toeplitz matrices scales linearly in the sparsity up to a $\log$-factor in the
ambient dimension. This represents a significant improvement over previous
recovery results for such matrices. As a main tool for the proofs we use a new
version of the non-commutative Khintchine inequality.
