Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary @math . This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary, if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the @math -restricted isometry property ( @math -RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in @math . While many classes of random matrices are known to satisfy such conditions, such matrices are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the @math -RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary @math . We also extend this analysis to allow for weighted sparse expansions. Consequently, we arrive at compressive sensing recovery guarantees for structured measurements and redundant dictionaries, opening the door to a wide array of practical applications.
Due to the abundance of relevant applications, a number of works have studied compressive sensing for overcomplete frames. The first work on this topic aimed to recover the coefficient vector @math directly, and thus required strong incoherence assumptions on the dictionary @math @cite_45 . More recently, it was noted that if one instead aims to recover @math rather than @math , recovery guarantees can be obtained under weaker assumptions. Namely, one only needs that the measurement matrix @math respects the norms of signals which are sparse in the dictionary @math . To quantify this, Cand @cite_25 define the @math -restricted isometry property ( @math -RIP in short, see Definition below). For measurement matrices that have this property, a number of algorithms have been shown to guarantee recovery under certain assumptions. Optimization approaches such as @math -analysis @cite_2 @cite_25 @cite_14 @cite_52 @cite_0 @cite_35 @cite_28 and greedy approaches @cite_56 @cite_14 @cite_11 @cite_71 @cite_69 have been studied.
@cite_35 @cite_69 @cite_14 @cite_28 @cite_52 @cite_56 @cite_0 @cite_45 @cite_71 @cite_2 @cite_25 @cite_11
2953076353 2949964595 2137959902 2105877514 2962817023
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. Compressive sampling (CoSa) is a new methodology which demonstrates that sparse signals can be recovered from a small number of linear measurements. Greedy algorithms like CoSaMP have been designed for this recovery, and variants of these methods have been adapted to the case where sparsity is with respect to some arbitrary dictionary rather than an orthonormal basis. In this work we present an analysis of the so-called Signal Space CoSaMP method when the measurements are corrupted with mean-zero white Gaussian noise. We establish near-oracle performance for recovery of signals sparse in some arbitrary dictionary. In addition, we analyze the block variant of the method for signals whose supports obey a block structure, extending the method into the model-based compressed sensing framework. Numerical experiments confirm that the block method significantly outperforms the standard method in these settings. Compressed sensing with sparse frame representations is seen to have much greater range of practical applications than that with orthonormal bases. In such settings, one approach to recover the signal is known as l1-analysis. We expand in this paper the performance analysis of this approach by providing a weaker recovery condition than existing results in the literature. Our analysis is also broadly based on general frames and alter native dual frames (as analysis operators). As one application to such a general-dual-based approach and performance analysis, an optimal-dual-based technique is proposed to demonstrate the effectiveness of using alternative dual frames as l1-analysis operators. An iterative algorithm is outlined for solving the optimal-dual-based -analysis problem. The effectiveness of the proposed method and algorithm is demonstrated through several experiments. This paper extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via basis pursuit (BP) from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing, and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments. Abstract Compressive sampling (CoSa) has provided many methods for signal recovery of signals compressible with respect to an orthonormal basis. However, modern applications have sparked the emergence of approaches for signals not sparse in an orthonormal basis but in some arbitrary, perhaps highly overcomplete, dictionary. Recently, several “signal-space” greedy methods have been proposed to address signal recovery in this setting. However, such methods inherently rely on the existence of fast and accurate projections which allow one to identify the most relevant atoms in a dictionary for any given signal, up to a very strict accuracy. When the dictionary is highly overcomplete, no such projections are currently known; the requirements on such projections do not even hold for incoherent or well-behaved dictionaries. In this work, we provide an alternate analysis for signal space greedy methods which enforce assumptions on these projections which hold in several settings including those when the dictionary is incoherent or structurally coherent. These results align more closely with traditional results in the standard CoSa literature and improve upon previous work in the signal space setting.