A Caltech Library Service

Analyzing Weighted ℓ_1 Minimization for Sparse Recovery With Nonuniform Sparse Models

Khajehnejad, M. Amin and Xu, Weiyu and Avestimehr, A. Salman and Hassibi, Babak (2011) Analyzing Weighted ℓ_1 Minimization for Sparse Recovery With Nonuniform Sparse Models. IEEE Transactions on Signal Processing, 59 (5). pp. 1985-2001. ISSN 1053-587X.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 IEEE. Manuscript received March 27, 2010; revised September 21, 2010, December 25, 2010; accepted January 06, 2011. Date of publication January 28, 2011; date of current version April 13, 2011. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Namrata Vaswani. This work was supported in part by the National Science Foundation under Grants CCF-0729203, CNS-0932428, and CCF-1018927, by the Office of Naval Research under the MURI Grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking. The results of this paper were presented in part at the International Symposium on Information Theory (ISIT), 2009.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Caltech Lee Center for Avanced NetworkingUNSPECIFIED
Subject Keywords:Compressed sensing; nonuniform sparsity; ℓ1 minimization
Issue or Number:5
Record Number:CaltechAUTHORS:20110502-112413009
Persistent URL:
Official Citation:Khajehnejad, M.A.; Weiyu Xu; Avestimehr, A.S.; Hassibi, B.; "Analyzing Weighted ℓ_1 Minimization for Sparse Recovery With Nonuniform Sparse Models," Signal Processing, IEEE Transactions on , vol.59, no.5, pp.1985-2001, May 2011 doi: 10.1109/TSP.2011.2107904
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23523
Deposited By: Jason Perez
Deposited On:02 May 2011 23:02
Last Modified:03 Oct 2019 02:47

Repository Staff Only: item control page