# High-dimensional Variable Selection with Sparse Random Projections: Measurement Sparsity and Statistical Efficiency

Dapo Omidiran, Martin J. Wainwright.

Year: 2010, Volume: 11, Issue: 82, Pages: 2361−2386

#### Abstract

We consider the problem of high-dimensional variable selection: given
*n* noisy observations of a *k*-sparse vector *β ^{*} ∈ R^{p}*,
estimate the subset of non-zero entries of

*β*. A significant body of work has studied behavior of

^{*}*l*-relaxations when applied to random measurement matrices that are dense (e.g., Gaussian, Bernoulli). In this paper, we analyze

_{1}*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 correct variable selection with probability converging to one. Our main result is to prove that it is possible to let the fraction on non-zero entries

*γ → 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.