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.
https://resolver.caltech.edu/CaltechAUTHORS:20120828-151151611

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20120828-151151611

## Abstract

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: | |||||||||||||

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. | ||||||||||||

Funders: |
| ||||||||||||

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: | https://resolver.caltech.edu/CaltechAUTHORS:20120828-151151611 | ||||||||||||

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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6283717&isnumber=6281806 | ||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||

ID Code: | 33623 | ||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | Ruth Sustaita | ||||||||||||

Deposited On: | 29 Aug 2012 16:41 | ||||||||||||

Last Modified: | 03 Oct 2019 04:11 |

Repository Staff Only: item control page