Oracle-order Recovery Performance of Greedy Pursuits with Replacement against General Perturbations
arXiv:1203.1521 · doi:10.1109/TSP.2013.2272551
Abstract
Applying the theory of compressive sensing in practice always takes different kinds of perturbations into consideration. In this paper, the recovery performance of greedy pursuits with replacement for sparse recovery is analyzed when both the measurement vector and the sensing matrix are contaminated with additive perturbations. Specifically, greedy pursuits with replacement include three algorithms, compressive sampling matching pursuit (CoSaMP), subspace pursuit (SP), and iterative hard thresholding (IHT), where the support estimation is evaluated and updated in each iteration. Based on restricted isometry property, a unified form of the error bounds of these recovery algorithms is derived under general perturbations for compressible signals. The results reveal that the recovery performance is stable against both perturbations. In addition, these bounds are compared with that of oracle recovery--- least squares solution with the locations of some largest entries in magnitude known a priori. The comparison shows that the error bounds of these algorithms only differ in coefficients from the lower bound of oracle recovery for some certain signal and perturbations, as reveals that oracle-order recovery performance of greedy pursuits with replacement is guaranteed. Numerical simulations are performed to verify the conclusions.
arXiv comment27 pages, 4 figures, 5 tables
References in corpus (19)
- Rejoinder to "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Least Angle Regression
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Simultaneous analysis of Lasso and Dantzig selector
- A fast approach for overcomplete sparse decomposition based on smoothed L0 norm
- Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling
- General Deviants: An Analysis of Perturbations in Compressed Sensing
- Coherence-Based Performance Guarantees for Estimating a Sparse Vector Under Random Noise
- A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework
- Compressed sensing performance bounds under Poisson noise
- Perturbation Analysis of Orthogonal Matching Pursuit
- Proof of Convergence and Performance Analysis for Sparse Recovery via Zero-point Attracting Projection