# Circulant and Toeplitz Matrices in Compressed Sensing

Abstract : 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.
Document type :
Conference papers
Domain :

Cited literature [23 references]

https://hal.inria.fr/inria-00369580
Contributor : Ist Rennes <>
Submitted on : Friday, March 20, 2009 - 1:47:48 PM
Last modification on : Thursday, February 7, 2019 - 2:24:09 PM
Long-term archiving on: : Friday, October 12, 2012 - 2:01:30 PM

### File

32.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : inria-00369580, version 1

### Citation

Holger Rauhut. Circulant and Toeplitz Matrices in Compressed Sensing. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Inria Rennes - Bretagne Atlantique, Apr 2009, Saint Malo, France. ⟨inria-00369580⟩

Record views