text: In this paper we consider memoryless one-bit compressed sensing with randomly subsampled Gaussian circulant matrices. We show that in a small sparsity regime and for small enough accuracy @math , @math measurements suffice to reconstruct the direction of any @math -sparse vector up to accuracy @math via an efficient program. We derive this result by proving that partial Gaussian circulant matrices satisfy an @math RIP-property. Under a slightly worse dependence on @math , we establish stability with respect to approximate sparsity, as well as full vector recovery results.
  @cite_16: 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 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 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.
  @cite_6: We discuss the use of random convolutions for Compressed Sensing applications. In particular, we will show that after convolving anN -dimensional,s-sparse signal with a Rademacher or Steinhaus sequence, it can be recovered via l1-minimization using only m & s log(N=") arbitrary chosen samples with probability at least 1 ".
  @cite_11: 
summary: Non-uniform recovery results have been shown in @cite_16 @cite_11 @cite_6 which require only @math measurements for exact recovery from (deterministically) subsampled random convolutions via @math -minimization.