Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
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


Files produced by the author(s)


  • HAL Id : inria-00369580, version 1



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


Files downloads