2010/09/18 by M. Amin Khajehnejad, Khajehnejad, M. Amin, Weiyu Xu +6 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1009.3525
arxiv created 2010/09/18 · openalex publication_date 2010/09/18 · arxiv updated 2010/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted ℓ1 minimization over that sparsity model. In particular, we focus on a model where the entries of the unknown vector fall into two sets, with entries of each set having a specific probability of being nonzero. We propose a weighted ℓ1 minimization recovery algorithm and analyze its performance using a Grassmann angle approach. We compute explicitly the relationship between the system parameters-the weights, the number of measurements, the size of the two sets, the probabilities of being nonzero- so that when i.i.d. random Gaussian measurement matrices are used, the weighted ℓ1 minimization recovers a randomly selected signal drawn from the considered sparsity model with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We demonstrate through rigorous analysis and simulations that for the case when the support of the signal can be divided into two different subclasses with unequal sparsity fractions, the optimal weighted ℓ1 minimization outperforms the regular ℓ1 minimization substantially. We also generalize the results to an arbitrary number of classes.