2008/05/20 by Dapo Omidiran, Martin J. Wainwright, Omidiran, Dapo +1 · 1 citation
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #stat.ML
paper · pdf · doi:10.48550/arxiv.0805.3005
arxiv created 2008/05/20 · openalex publication_date 2008/05/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of estimating the support of a vector β^* ∈ ℝp based on observations contaminated by noise. A significant body of work has studied behavior of ℓ1-relaxations when applied to measurement matrices drawn from standard dense ensembles (e.g., Gaussian, Bernoulli). In this paper, we analyze 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 γ→ 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.