Perturbations of measurement matrices and dictionaries in compressed sensing

The compressed sensing problem for redundant dictionaries aims to use a small number of linear measurements to represent signals that are sparse with respect to a general dictionary. Under an appropriate restricted isometry property for a dictionary, reconstruction methods based on ℓq minimization are known to provide an effective signal recovery tool in this setting. This note explores conditions under which ℓq minimization is robust to measurement noise, and stable with respect to perturbations of the sensing matrix A and the dictionary D. We propose a new condition, the D null space property, which guarantees that ℓq minimization produces solutions that are robust and stable against perturbations of A and D. We also show that ℓq minimization is jointly stable with respect to imprecise knowledge of the measurement matrix A and the dictionary D when A satisfies the restricted isometry property.