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.
In other relevant works @cite_4 @cite_33 , the error bounds of CoSaMP and SP are also derived under general perturbations. The analysis is performed following the steps of @cite_3 for basis pursuit. Define The main result in @cite_4 states that under the conditions that and the recovered solution of CoSaMP satisfies Further define where The main result in @cite_33 states that under the conditions that and that the recovered solution of SP satisfies
@cite_4 @cite_33 @cite_3
2039851473 1561053739 2129131372 2112502349
This correspondence presents an average case denoising performance analysis for SP, CoSaMP, and IHT algorithms. This analysis considers the recovery of a noisy signal, with the assumptions that it is corrupted by an additive random zero-mean white Gaussian noise and has a K-sparse representation with respect to a known dictionary D . The proposed analysis is based on the RIP, establishing a near-oracle performance guarantee for each of these algorithms. Beyond bounds for the reconstruction error that hold with high probability, in this work we also provide a bound for the average error. In this paper, the Subspace Pursuit (SP) recovery of signals with sensing matrix perturbations is analyzed. Previous studies have only considered the robustness of Basis pursuit and greedy algorithms to recover the signal in the presence of additive noise with measurement and or signal. Since it is impractical to exactly implement the sampling matrix A in a physical sensor, precision errors must be considered. Recently, work has been done to analyze the methods with noise in the sampling matrix, which generates a multiplicative noise term. This new perturbed framework (both additive and multiplicative noise) extends the prior work of Basis pursuit and greedy algorithms on stable signal recovery from incomplete and inaccurate measurements. Our works show that, under reasonable conditions, the stability of the SP solution of the completely perturbed scenario was limited by the total noise in the observation. This paper considers a natural error correcting problem with real valued input output. We wish to recover an input vector f spl isin R sup n from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the spl lscr sub 1 -minimization problem ( spl par x spl par sub spl lscr 1 := spl Sigma sub i |x sub i |) min(g spl isin R sup n ) spl par y - Ag spl par sub spl lscr 1 provided that the support of the vector of errors is not too large, spl par e spl par sub spl lscr 0 :=| i:e sub i spl ne 0 | spl les spl rho spl middot m for some spl rho >0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of spl lscr sub 1 is a crucial property we call the uniform uncertainty principle that we shall describe in detail. We consider the problem of the reconstruction of a continuous-time function f(x) spl isin H from the samples of the responses of m linear shift-invariant systems sampled at 1 m the reconstruction rate. We extend Papoulis' generalized sampling theory in two important respects. First, our class of admissible input signals (typ. H=L sub 2 ) is considerably larger than the subspace of band-limited functions. Second, we use a more general specification of the reconstruction subspace V( spl psi ), so that the output of the system can take the form of a band-limited function, a spline, or a wavelet expansion. Since we have enlarged the class of admissible input functions, we have to give up Shannon and Papoulis' principle of an exact reconstruction. Instead, we seek an approximation f spl isin V( spl psi ) that is consistent in the sense that it produces exactly the same measurements as the input of the system. This leads to a generalization of Papoulis' sampling theorem and a practical reconstruction algorithm that takes the form of a multivariate filter. In particular, we show that the corresponding system acts as a projector from H onto V( spl psi ). We then propose two complementary polyphase and modulation domain interpretations of our solution. The polyphase representation leads to a simple understanding of our reconstruction algorithm in terms of a perfect reconstruction filter bank. The modulation analysis, on the other hand, is useful in providing the connection with Papoulis' earlier results for the band-limited case. Finally, we illustrate the general applicability of our theory by presenting new examples of interlaced and derivative sampling using splines.