Weighted one-norm minimization with inaccurate support estimates: Sharp analysis via the null-space property
Abstract
We study the problem of recovering sparse vectors given possibly erroneous support estimates. First, we provide necessary and sufficient conditions for weighted ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization to successfully recovery all sparse signals whose support estimate is sufficiently accurate. We relate these conditions to the analogous ones for ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization, showing that they are equivalent when the support estimate is 50% accurate but that the weighted ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> 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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization succeeds. The resulting number of measurements can be significantly less than what is needed to ensure recovery via ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> minimization. Finally, we illustrate our results via numerical experiments.
BibTeX
@inproceedings{icassp2015_weightedonenormm,
title = {Weighted one-norm minimization with inaccurate support estimates: Sharp analysis via the null-space property},
author = {Hassan Mansour and Rayan Saab},
booktitle = {ICASSP 2015},
year = {2015}
}