Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2012 | public
Book Section - Chapter

Recovery Threshold for Optimal Weight ℓ_1 Minimization

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.

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.

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024