Volume 41, pp. 167-178, 2014.

Nonuniform Sparse Recovery with Subgaussian Matrices

Ulaç 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], BibTeX

Key words

compressed sensing, sparse recovery, random matrices, ${\ell }_1$-minimization

AMS subject classifications

94A20, 60B20