Computer Science – Information Theory
Scientific paper
2009-02-25
Computer Science
Information Theory
6 pages, submitted to Proc. SPARS'09 (Saint-Malo)
Scientific paper
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.
No associations
LandOfFree
Circulant and Toeplitz matrices in compressed sensing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Circulant and Toeplitz matrices in compressed sensing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circulant and Toeplitz matrices in compressed sensing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-158149