## Nonuniform Sparse Recovery with Subgaussian Matrices

Ulaç Ayaz and Holger Rauhut

### Abstract

Compressive sensing predicts that sufficiently sparse vectors can be recovered from highly incomplete information using efficient recovery methods such as $\ell_1$-minimization. Random matrices have become a popular choice for the measurement matrix. Indeed, near-optimal uniform recovery results have been shown for such matrices. In this note we focus on nonuniform recovery using subgaussian random matrices and $\ell_1$-minimization. We provide conditions on the number of samples in terms of the sparsity and the signal length which guarantee that a fixed sparse signal can be recovered with a random draw of the matrix using $\ell_1$-minimization. Our proofs are short and provide explicit and convenient constants.

Full Text (PDF) [161 KB]

### Key words

compressed sensing, sparse recovery, random matrices, $\ell_1$-minimization

94A20, 60B20

< Back