Recovery Analysis for Weighted $\\ell_1$-Minimization Using a Null Space\n Property

We study the recovery of sparse signals from underdetermined linear\nmeasurements when a potentially erroneous support estimate is available. Our\nresults are twofold. First, we derive necessary and sufficient conditions for\nsignal recovery from compressively sampled measurements using weighted\n$\\ell_1$-norm minimization. These conditions, which depend on the choice of\nweights as well as the size and accuracy of the support estimate, are on the\nnull space of the measurement matrix. They can guarantee recovery even when\nstandard $\\ell_1$ minimization fails. Second, we derive bounds on the number of\nGaussian measurements for these conditions to be satisfied, i.e., for weighted\n$\\ell_1$ minimization to successfully recover all sparse signals whose support\nhas been estimated sufficiently accurately. Our bounds show that weighted\n$\\ell_1$ minimization requires significantly fewer measurements than standard\n$\\ell_1$ minimization when the support estimate is relatively accurate.\n