Nonuniform sparse recovery with subgaussian matrices
Electronic transactions on numerical analysis, Tome 41 (2014), pp. 167-178
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.
Classification :
94A20, 60B20
Keywords: compressed sensing, sparse recovery, random matrices, $\ell_1$-minimization
Keywords: compressed sensing, sparse recovery, random matrices, $\ell_1$-minimization
@article{ETNA_2014__41__a15,
author = {Ayaz, Ula\c{s} and Rauhut, Holger},
title = {Nonuniform sparse recovery with subgaussian matrices},
journal = {Electronic transactions on numerical analysis},
pages = {167--178},
year = {2014},
volume = {41},
zbl = {1306.94013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ETNA_2014__41__a15/}
}
Ayaz, Ulaş; Rauhut, Holger. Nonuniform sparse recovery with subgaussian matrices. Electronic transactions on numerical analysis, Tome 41 (2014), pp. 167-178. http://geodesic.mathdoc.fr/item/ETNA_2014__41__a15/