Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have considered the recovery of a sparse signal through Φ and y = Φx + b, where is a matrix with more columns than rows and denotes the measurement noise. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means both y and Φ are perturbed. Though the exact recovery of an almost sparse signal x is no longer feasible, the main contribution reveals that the support set of the best k-term approximation of x can be recovered under reasonable conditions. The error bound between x and the estimation of OMP is also derived. By constructing an example it is also demonstrated that the sufficient conditions for support recovery of the best k-term approximation of are rather tight. When x is strong-decaying, it is proved that the sufficient conditions for support recovery of the best k-term approximation of x can be relaxed, and the support can even be recovered in the order of the entries' magnitude. Our results are also compared in detail with some related previous ones.
Despite the difference in requirements, the recovery errors given in Theorem 2 of @cite_3 and Corollary @math are the same, since these errors are both derived when the support set of the sparse signal is perfectly recovered.
@cite_3
2953076353 2096586829 1620362451 2964167436
This paper provides novel results for the recovery of signals from undersampled measurements based on analysis @math -minimization, when the analysis operator is given by a frame. We both provide so-called uniform and nonuniform recovery guarantees for cosparse (analysis-sparse) signals using Gaussian random measurement matrices. The nonuniform result relies on a recovery condition via tangent cones and the uniform recovery guarantee is based on an analysis version of the null space property. Examining these conditions for Gaussian random matrices leads to precise bounds on the number of measurements required for successful recovery. In the special case of standard sparsity, our result improves a bound due to Rudelson and Vershynin concerning the exact reconstruction of sparse signals from Gaussian measurements with respect to the constant and extends it to stability under passing to approximately sparse signals and to robustness under noise on the measurements. This paper studies the problem of recovering a sparse signal x ∈ ℝn from highly corrupted linear measurements y = Ax + e ∈ ℝm, where e is an unknown error vector whose nonzero entries may be unbounded. Motivated by an observation from face recognition in computer vision, this paper proves that for highly correlated (and possibly overcomplete) dictionaries A, any sufficiently sparse signal x can be recovered by solving an l1 -minimization problem min ||x||1 + ||e||1 subject to y = Ax + e. More precisely, if the fraction of the support of the error e is bounded away from one and the support of a: is a very small fraction of the dimension m, then as m becomes large the above l1 -minimization succeeds for all signals x and almost all sign-and-support patterns of e. This result suggests that accurate recovery of sparse signals is possible and computationally feasible even with nearly 100 of the observations corrupted. The proof relies on a careful characterization of the faces of a convex polytope spanned together by the standard crosspolytope and a set of independent identically distributed (i.i.d.) Gaussian vectors with nonzero mean and small variance, dubbed the "cross-and-bouquet" (CAB) model. Simulations and experiments corroborate the findings, and suggest extensions to the result. There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach utilizes geometric properties of the measurement matrix Phi. A notable example is the Restricted Isometry Property, which states that the mapping Phi preserves the Euclidean norm of sparse signals; it is known that random dense matrices satisfy this constraint with high probability. On the other hand, the combinatorial approach utilizes sparse matrices, interpreted as adjacency matrices of sparse (possibly random) graphs, and uses combinatorial techniques to recover an approximation to the signal. In this paper we present a unification of these two approaches. To this end, we extend the notion of Restricted Isometry Property from the Euclidean lscr2 norm to the Manhattan lscr1 norm. Then we show that this new lscr1 -based property is essentially equivalent to the combinatorial notion of expansion of the sparse graph underlying the measurement matrix. At the same time we show that the new property suffices to guarantee correctness of both geometric and combinatorial recovery algorithms. As a result, we obtain new measurement matrix constructions and algorithms for signal recovery which, compared to previous algorithms, are superior in either the number of measurements or computational efficiency of decoders. Most of the existing sparse-recovery methods assume a static system: the signal is a finite-length vector for which a fixed set of measurements and sparse representation are available and an l1 problem is solved for the reconstruction. However, the same representation and reconstruction framework is not readily applicable in a streaming system: the signal changes over time, and it is measured and reconstructed sequentially over small intervals. This is particularly desired when dividing signals into disjoint blocks and processing each block separately is infeasible or inefficient. In this paper, we discuss two streaming systems and a new homotopy algorithm for quickly solving the associated l1 problems: 1) recovery of smooth, time-varying signals for which, instead of using block transforms, we use lapped orthogonal transforms for sparse representation and 2) recovery of sparse, time-varying signals that follows a linear dynamic model. For both systems, we iteratively process measurements over a sliding interval and solve a weighted l1-norm minimization problem for estimating sparse coefficients. Since we estimate overlapping portions of the signal while adding and removing measurements, instead of solving a new l1 program as the system changes, we use available signal estimates as starting point in a homotopy formulation and update the solution in a few simple steps. We demonstrate with numerical experiments that our proposed streaming recovery framework provides better reconstruction compared to the methods that represent and reconstruct signals as independent, disjoint blocks, and that our proposed homotopy algorithm updates the solution faster than the current state-of-the-art solvers.