Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices
| dc.creator | Wang, Wei | |
| dc.creator | Wainwright, Martin J. | |
| dc.creator | Ramchandran, Kannan | |
| dc.date | 2008-06-03 | |
| dc.date.accessioned | 2026-07-07T09:42:27Z | |
| dc.date.available | 2026-07-07T09:42:27Z | |
| dc.description | We study the information-theoretic limits of exactly recovering the support of a sparse signal using noisy projections defined by various classes of measurement matrices. Our analysis is high-dimensional in nature, in which the number of observations $n$, the ambient signal dimension $p$, and the signal sparsity $k$ are all allowed to tend to infinity in a general manner. This paper makes two novel contributions. First, we provide sharper necessary conditions for exact support recovery using general (non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields sharp characterizations of when the optimal decoder can recover a signal for various scalings of the sparsity $k$ and sample size $n$, including the important special case of linear sparsity ($k = Θ(p)$) using a linear scaling of observations ($n = Θ(p)$). Our second contribution is to prove necessary conditions on the number of observations $n$ required for asymptotically reliable recovery using a class of $γ$-sparsified measurement matrices, where the measurement sparsity $γ(n, p, k) \in (0,1]$ corresponds to the fraction of non-zero entries per row. Our analysis allows general scaling of the quadruplet $(n, p, k, γ)$, and reveals three different regimes, corresponding to whether measurement sparsity has no effect, a minor effect, or a dramatic effect on the information-theoretic limits of the subset recovery problem. | |
| dc.description | Appeared as UC Berkeley, Department of Statistics, Technical Report | |
| dc.identifier | https://arxiv.org/abs/0806.0604 | |
| dc.identifier | http://arxiv.org/abs/0806.0604 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162186 | |
| dc.subject | Statistics Theory | |
| dc.subject | Information Theory | |
| dc.title | Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices | |
| dc.type | text |