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 ${\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.

6 pages, submitted to Proc. SPARS'09 (Saint-Malo)

References in corpus (10)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al

Cited by in corpus (6)

• Johnson-Lindenstrauss lemma for circulant matrices
• Compressive sensing by white random convolution
• Toeplitz Matrix Based Sparse Error Correction in System Identification: Outliers and Random Noises
• Compressive Signal Processing with Circulant Sensing Matrices
• Deterministic partial binary circulant compressed sensing matrices
• An Introduction to Johnson-Lindenstrauss Transforms