A Study On Greedy Reconstruction Algorithms For Compressed Sensing

Compressed sensing is a new sampling compression technology in recent year, which has broken the traditional Nyquist sampling theorem. It can sample signal and compress data at the same time, and now it has made great process. Compressed sensing is made of two parts. One is to sample signal, the other is to reconstruct original signal. The first one is to acquire low dimensional measurements through measurement matrix for high dimensional sparse signals or compressible signal. The latter one is to use these low dimensional data to recover original sparse signal. Reconstruction algorithm is an important step for compressed sensing, deciding the quality of reconstructed signal. This thesis is based on classic greedy algorithms, researching every algorithm in detail, analyzing their merits and demerits and improving deficiencies. After this, the thesis puts forward some algorithms which have better performance.Firstly, this thesis summarizes and introduces some popular greedy algorithms. These algorithms consist of two parts. The first one is researching two matching pursuit algorithms according to the bottom-up principle, the second one is studying two matching pursuit algorithms according to the top-down principle. This thesis introduces all kinds of algorithms in detail, analyzing their advantage and disadvantage. After the theoretical description, there will be some experimental results to verify the theoretical analysis.Secondly, the-thesis puts forward a new compressed sensing reconstruction algorithm called backtracking regularized adaptive matching pursuit algorithm, which is based on summarizing regularized orthogonal matching pursuit and regularized adaptive matching pursuit algorithm. This modified algorithm can well reconstruct sparse signal when the sparsity is unknown. First the method adaptively chooses some atoms through setting fuzzy threshold way, then retaining regularized process to choose some atoms again. At last, using backtracking way to delete some wrong atoms. The support set is updated while it is being enlarged gradually in every iteration, so it can approximate the sparsity of signal. Compared with regularized adaptive matching pursuit algorithm, this algorithm adds backtracking process, its reconstruction result greatly improve. The experimental result also demonstrates this point.At last, after fully comparing two orthogonal reconstruction algorithms, this thesis puts forward a new compressed sensing greedy reconstruction algorithm, which is called generalized orthogonal least squares algorithm. This algorithm fully integrates the idea of generalized orthogonal matching pursuit and use residual value to select multiple high-quality atoms once a time. In this way, the reconstruction accuracy and complexity are improved. Since this algorithm makes selected atoms repeatedly proceed orthogonal projection at each iteration, which leads to high computational complexity. This thesis later uses projection theorem and trigonometry to equivalently substitute the atom selection step. Let original comparing residual value process transform into calculating the size of correlation. Then in each iteration this algorithm only needs once orthogonal projection and it can finish atomic filter. Not only can maintain original signal reconstruction quality, but also greatly reduce computational complexity.