Research On Measurement Matrix And Recovery Algorithm In Compressive Sensing

The thesis mainly focused on the recent theory of Compressed Sensing(CS), which was put forward by Candes,Tao,Romberg,Donoho etc. Different from Shanno n/Nyquist theorem, CS is a new approach to simultaneous sensing and compression that enables a potentially large reduction in the sampling rate. Signals having a sparse or compressible representation in some basis can be recovered from what was previously believed to be highly incomplete measurements(information) with high probability. CS is still at the beginning of research, but as a new type of sampling theory and new technology, it has been widely used in signal and image processing etc.Around this emerging theory, this thesis mainly aims at the measurement matrix and reconstruction algorithm of CS, does some related research:(1) Aims at random measurements matrices are often diffcult and costly to implement in hardware realizations, the thesis introduces sparse banded and column measurements matrix for reconstructing signals that the independent random variables are reduced more than one-third. (2) We introduce the the main reconstruction algorithms, constructing an algorithm comparison platform. (3) The backtracking-based iterative hard thresholding (BIHT) algorithm is proposed in this thesis to solve the problem that the iteration times are too much and the time is too long of the iterative hard thresholding (IHT) algorithm when applied to the compressive sensing. BIHT algorithm ensures the reconstruction quality and decreases two orders of magnitude of time when compared with IHT algorithms for the low noise level. (4) Applied sparse banded measurements matrix and BIHT algorithm to reconstruct two-dimensional image, the image reconstruction time and signal-to-noise ratio are improved. The main research works and contributions of this dissertation are outlined as follows.(1) Aimed at one of the key components in compressed sensing-measurements matrix, most work so far focuses on Gaussian or Bernoulli random measurements. Since in theory, the optimal incoherence is achieved by completely random meas urement matrices. However, such matrices are often diffcult and costly to implement in hardware realizations. The use of random circulant and Toeplitz matrices reduces the necessary independent random variables. What's more, random Toeplitz and circulant matrix can be easily (or even naturally) realized in various applications. This thesis introduces sparse banded and column measurements matrix for reconstructing signals that independent random variables be reduced more than one-third.. At last, simulation experiments show that the the reconstruction effect and the probability of our sparse matrix are the same as random matrix.(2) Because efficient algorithms such as l1-minimization and greedy algorithms can be used for recovery, as a main feature. Here, we summarize the main reconstruction algorithms, including MP,OMP,MBOOMP. ROMP,STOMP,IHT,CoSaMP,SP, etc iterative algorithms, constructing an algorithm comparison platform. Meanwhile, the simulation of radom signal which is composed of 0 and 1 are adapted to compare their performance. It is shown that SP and CoSaMP are better than other algorithm.(3) The backtracking-based iterative hard thresholding (BIHT) algorithm is proposed to solve the problem that the iteration times are too much and the time is too long of the iterative hard thresholding (IHT) algorithm when is applied to the compressive sensing. BIHT algorithm optimizes the sub-optimal choice of supports for each iteration and reduces the times of some supports iterated repeatedly by adding the idea of backtracking. The simulation demonstrate that backtracking-based algorithm ensures the reconstruction quality and decreases two orders of magnitude of time when compared with IHT and NIHT algorithms for the low noise level. Simulation on the 0-1 sparse signal demonstrate that the reconstruction probability of BIHT algorithm is higher than that of the IHT algorithm if the measurement times and sparsity of the signal are the same.(4) We studied the reconstruction of two-dimensional images. When the size of image is too large to storage, we reconstruct the image by using sparse banded measurements matrix and BIHT algorithm in each column. We compared random and sparse banded measurements matrix plus SP and BIHT algorithm, experimental results show that image reconstruction time and signal-to-noise ratio of parse banded matrix plus BIHT algorithm are better than others.