High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency
| dc.creator | Omidiran, Dapo | |
| dc.creator | Wainwright, Martin J. | |
| dc.date | 2008-05-20 | |
| dc.date.accessioned | 2026-07-07T09:39:50Z | |
| dc.date.available | 2026-07-07T09:39:50Z | |
| dc.description | We consider the problem of estimating the support of a vector $β^* \in \mathbb{R}^{p}$ based on observations contaminated by noise. A significant body of work has studied behavior of $\ell_1$-relaxations when applied to measurement matrices drawn from standard dense ensembles (e.g., Gaussian, Bernoulli). In this paper, we analyze \emph{sparsified} measurement ensembles, and consider the trade-off between measurement sparsity, as measured by the fraction $γ$ of non-zero entries, and the statistical efficiency, as measured by the minimal number of observations $n$ required for exact support recovery with probability converging to one. Our main result is to prove that it is possible to let $γ\to 0$ at some rate, yielding measurement matrices with a vanishing fraction of non-zeros per row while retaining the same statistical efficiency as dense ensembles. A variety of simulation results confirm the sharpness of our theoretical predictions. | |
| dc.identifier | https://arxiv.org/abs/0805.3005 | |
| dc.identifier | http://arxiv.org/abs/0805.3005 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/161325 | |
| dc.subject | Machine Learning | |
| dc.subject | Information Theory | |
| dc.title | High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency | |
| dc.type | text |