Journal article
Analyzing Weighted ℓ1 Minimization for Sparse Recovery With Nonuniform Sparse Models
IEEE transactions on signal processing, Vol.59(5), pp.1985-2001
2011
DOI: 10.1109/TSP.2011.2107904
Abstract
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 weighted ℓ 1 minimization outperforms the regular ℓ 1 minimization substantially. We also generalize our results to signal vectors with an arbitrary number of subclasses for sparsity.
Details
- Title: Subtitle
- Analyzing Weighted ℓ1 Minimization for Sparse Recovery With Nonuniform Sparse Models
- Creators
- M Amin Khajehnejad - California Institute of Technology, Pasadena CA 91125, United StatesWEIYU XU - California Institute of Technology, Pasadena CA 91125, United StatesA. Salman Avestimehr - Cornell University, Ithaca NY 14853, United StatesBabak HASSIBI - California Institute of Technology, Pasadena CA 91125, United States
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on signal processing, Vol.59(5), pp.1985-2001
- Publisher
- Institute of Electrical and Electronics Engineers
- DOI
- 10.1109/TSP.2011.2107904
- ISSN
- 1053-587X
- eISSN
- 1941-0476
- Language
- English
- Date published
- 2011
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083251102771
Metrics
14 Record Views