Reconstruction Of The Sparse Signal In The Overcomplete Dictionary

Sparsity is a common phenomenon where a large data set may be succinctly represented or approximated using only a small number of summary values or coefficients. The presence of sparsity suggests the potential for efficient methods to extract only the relevant information, conserving acquisition and processing resources which can often be scarce or expensive. Compressive sensing(CS) is a novel sampling paradigm that leverages the concept of sparsity. CS theory asserts that one can reconstruct certain signals from far fewer samples or measurements than the sampling theorem requires. The existing theory of CS framework assumes the underlying signal has a sparse representation in an orthonormal basis. This cannot meet to the requirement of wide range of applications. On the other hand, there are numerous practical examples where a signal of interest is not sparse in an orthonormal basis but rather in an overcomplete dictionary. Since allowing the signal to be sparse with respect to a redundant dictionary adds a lot of flexibility and significantly extends the range of applicability. Moreover, due to the flexibility and convenience offered by overcomplete representations, overcomplete representations are extremely helpful in reducing artifacts and mean squared error and could effectively sparsify the signals. Our working extends the application scope of compressive sensing to signals that are not sparse in an orthonormal basis but rather in the overcomplete dictionary and explores the reconstruction of sparse signal in the overcomplete dictionary. We establish a completely perturbed noise model to examine the effect of different types of noise in different practical sampling schemes on the accuracy of signal reconstruction. Application of some proposing algorithms on the signal that is the sparse in wavelet domain is also demonstrated. Our key contributions include:(1) Reconstruction error is partly determined by the joint properties of sensing matrix and sparsifying matrix. Since the existing tools does not provide complete information on joint properties of sensing matrix and sparsifying matrix. We propose two new statistics tools to analysis sensing matrix and sparsifying matrix pairs. They are Histogram statistics, which conveys more local information and Group counting, which provides global information on well-conditionedness of the pairs. These tools provided accurate information reconstruction guarantees.(2) l1minimization of signal algorithm and l1minimization of coefficient algorithm have the algebraic similarity. We compare these two reconstruction algorithms from geometrical view. The optimal process of two algorithms is analyzed via high-dimensional polytopal geometry. The geometrical structures of two algorithms defining exhibit very different properties which could provide selection basis for the wide applications.(3) We introduce a completely perturbed noise model to examine the effect of different types of noise in different practical sampling schemes on the accuracy of signal reconstruction. As an optimal method, Least Squares linear estimator is used to analyze the effect of real-life noises on the reconstruction and to show that Restricted Isometry Constant is not the only factor that determines the reconstruction accuracy. The relation between sensing submatrix, noise and reconstruction error is given. We derive the error energy as a function of three noise types and different sensing submatrix. Compared with errors due to noise in directly sensing sparse signal, the error in CS scheme is relative smaller. When applications call for physically implementing the sensing matrix in a sensor, it is important to consider the noise in it. We analyze the effect of noise of sensing matrix on RIP and show that the penalty on the spectrum of sensing matrix submatrices is a linear function of the relative error. The results are verified by numerical simulations.(4) Since Basis Pursuit does not exploits the structure sparsity of signal. Based on exploiting interdependency structure among the wavelet coefficients of piecewise smooth signal, we develop a fast reconstruction algorithm--different weighted iteration method, which can reduce the computations and measurements. Furthermore, we generate the matrix corresponding to orthonormal wavelet transform. Based on that, matrix corresponding to overcomplete wavelet dictionary is given.(5) To prove the effectiveness of the proposed method, different weighted iteration method is used in the image denoising. we develop an image denoising method based on different weighted iteration method and optimal sparse representation. Our method denoises image from a local view and using a learning dictionary. We present some numerical experiments illustrating the effectiveness of our method and also compare the method to other alternatives.