arXiv Analytics

Sign in

arXiv:1009.3525 [cs.IT]AbstractReferencesReviewsResources

Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery with Nonuniform Sparse Models\footnote{The results of this paper were presented in part at the International Symposium on Information Theory, ISIT 2009}

M. Amin Khajehnejad, Weiyu Xu, A. Salman Avestimehr, Babak Hassibi

Published 2010-09-18Version 1

In this paper we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted $\ell_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 $\ell_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 $\ell_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 $\ell_1$ minimization outperforms the regular $\ell_1$ minimization substantially. We also generalize the results to an arbitrary number of classes.

Related articles: Most relevant | Search more
arXiv:1107.2984 [cs.IT] (Published 2011-07-15)
An Introductory Review of Information Theory in the Context of Computational Neuroscience
arXiv:2304.12482 [cs.IT] (Published 2023-04-24)
Information Theory for Complex Systems Scientists
arXiv:1010.3337 [cs.IT] (Published 2010-10-16)
How to use our talents based on Information Theory - or spending time wisely