Circulant and Toeplitz matrices in compressed sensing
| dc.creator | Rauhut, Holger | |
| dc.date | 2009-02-25 | |
| dc.date.accessioned | 2026-07-07T12:46:45Z | |
| dc.date.available | 2026-07-07T12:46:45Z | |
| dc.description | 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 $\ell_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 $\ell_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. | |
| dc.description | 6 pages, submitted to Proc. SPARS'09 (Saint-Malo) | |
| dc.identifier | https://arxiv.org/abs/0902.4394 | |
| dc.identifier | http://arxiv.org/abs/0902.4394 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/221489 | |
| dc.subject | Information Theory | |
| dc.title | Circulant and Toeplitz matrices in compressed sensing | |
| dc.type | text |