Abstract:

We study the problem of recovering sparse vectors given possibly erroneous support estimates. First, we provide necessary and sufficient conditions for weighted l1 minimization to successfully recovery all sparse signals whose support estimate is sufficiently accurate. We relate these conditions to the analogous ones for l1 minimization, showing that they are equivalent when the support estimate is 50% accurate but that the weighted l1 conditions are easier to satisfy when the support is more than 50% accurate. Second, to quantify this improvement, we provide bounds on the number of Gaussian measurements that ensure, with high probability, that weighted l1 minimization succeeds. The resulting number of measurements can be significantly less than what is needed to ensure recovery via l1 minimization. Finally, we illustrate our results via numerical experiments.