A Caltech Library Service

Recovery Threshold for Optimal Weight ℓ_1 Minimization

Oymak, Samet and Khajehnejad, M. Amin and Hassibi, Babak (2012) Recovery Threshold for Optimal Weight ℓ_1 Minimization. In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT). IEEE International Symposium on Information Theory Proceedings . IEEE , Piscataway, NJ, pp. 2032-2036. ISBN 978-1-4673-2580-6.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We consider the problem of recovering a sparse signal from underdetermined measurements when we have prior information about the sparsity structure of the signal. In particular, we assume that the entries of the signal can be partitioned into two known sets S_1, S_2 where the relative sparsities over the two sets are different. In this situation it is advantageous to replace classical ℓ_1 minimization with weighted ℓ_1 minimization, where the sparser set is given a larger weight. In this paper we give a simple closed form expression for the minimum number of measurements required for successful recovery when the optimal weights are chosen. The formula shows that the number of measurements is upper bounded by the sum of the minimum number of measurements needed had we measured the S_1 and S_2 components of the signal separately. In fact, our results indicate that this upper bound is tight and we actually have equality. Our proof technique uses the “escape through a mesh” framework and connects to the Minimax MSE of a certain basis pursuit denisoing problem.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2012 IEEE. Date of Current Version: 27 August 2012. 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.
Funding AgencyGrant Number
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI)N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:weighted ℓ_1 minimization, compressed sensing, basis pursuit denoising, sparse recovery
Series Name:IEEE International Symposium on Information Theory Proceedings
Record Number:CaltechAUTHORS:20120828-151151611
Persistent URL:
Official Citation:Oymak, Samet; Khajehnejad, M. Amin; Hassibi, Babak; , "Recovery threshold for optimal weight ℓ1 minimization," Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on , vol., no., pp.2032-2036, 1-6 July 2012 doi: 10.1109/ISIT.2012.6283717 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:33623
Deposited By: Ruth Sustaita
Deposited On:29 Aug 2012 16:41
Last Modified:03 Oct 2019 04:11

Repository Staff Only: item control page