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.
Type de document :
Communication dans un congrès
Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00369580
Contributeur : Ist Rennes <>
Soumis le : vendredi 20 mars 2009 - 13:47:48
Dernière modification le : lundi 20 juin 2016 - 14:10:32
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 14:01:30

Fichier

32.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00369580, version 1

Collections

Citation

Holger Rauhut. Circulant and Toeplitz Matrices in Compressed Sensing. Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009. 〈inria-00369580〉

Partager

Métriques

Consultations de la notice

232

Téléchargements de fichiers

268