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

摘要

We consider the problem of high-dimensional variable selection: givenn noisy observations of a k-sparse vector β* ∈ Rp,estimate the subset of non-zero entries of β*.A significant body of work has studied behavior ofl₁-relaxations when applied to random measurement matrices thatare dense (e.g., Gaussian, Bernoulli). In this paper, we analyzesparsified measurement ensembles, and consider the trade-offbetween measurement sparsity, as measured by the fraction γ ofnon-zero entries, and the statistical efficiency, as measured by theminimal number of observations n required for correct variableselection with probability converging to one. Our main result is toprove that it is possible to let the fraction on non-zero entriesγ → 0 at some rate, yielding measurement matriceswith a vanishing fraction of non-zeros per row, while retaining thesame statistical efficiency as dense ensembles. A variety ofsimulation results confirm the sharpness of our theoreticalpredictions. color="gray">