  In this paper, a new class of circulant matrices built from deterministic
sequences is proposed for convolution-based compressed sensing (CS). In
contrast to random convolution, the coefficients of the underlying filter are
given by the discrete Fourier transform of a deterministic sequence with good
autocorrelation. Both uniform recovery and non-uniform recovery of sparse
signals are investigated, based on the coherence parameter of the proposed
sensing matrices. Many examples of the sequences are investigated, particularly
the Frank-Zadoff-Chu (FZC) sequence, the \textit{m}-sequence and the Golay
sequence. A salient feature of the proposed sensing matrices is that they can
not only handle sparse signals in the time domain, but also those in the
frequency and/or or discrete-cosine transform (DCT) domain.
