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

** Dapo Omidiran, Martin J. Wainwright**; 11(Aug):2361−2386, 2010.

### Abstract

We consider the problem of high-dimensional variable selection: given*n*noisy observations of a

*k*-sparse vector

*β*, estimate the subset of non-zero entries of

^{*}∈ R^{p}*β*. 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.

[abs][pdf]