Greedy pursuits: Stability of recovery performance against general perturbations

Applying the theory of Compressive Sensing in practice must take different kinds of perturbations into consideration. In this paper, the recovery performance of greedy pursuits is analyzed when both the measurement vector and the sensing matrix are contaminated. Specifically, the error bounds of the solutions of CoSaMP, SP, and IHT are derived respectively, and these bounds are compared with oracle recovery - least squares solution with support known a priori. The results show that the bounds are almost proportional to both perturbations, and the three greedy algorithms can provide near-oracle recovery performance against general perturbations. Several numerical simulations verify this conclusion.