A Study Of Convex Relaxation Algorithms For Compressed Sensing Reconstruction Problem

The new signal processing method- compressed sensing theory is based on the sparse nature of the signal or compressible nature of the proposed. It broke the limited sampling rate Nyquist sampling theorem, abandoned the first sample and then compressed signal processing mode, so that the signal sampling process and compression process could happen at the same time. Signals can be restructured by solving optimization problems thus effectively eliminating the need of a large number of sample data, addressing the sampling data obtained storage, transmission and other high-cost problems, and bringing revolutionary progress for the realization of efficient signal processing. Compressed sensing theory contains three basic elements: sparse representation signal, the selection of the observation matrix and the reconstruction of algorithm design. The effect of reconstruction algorithm and convergence speed directly determines whether the theory is practicable. Therefore the core of compressed sensing theory is to design efficient reconstruction algorithms. This article is based on the study of compressed sensing theory and reconstruction algorithm with the content of the following aspects:Firstly, it states the research background and significance of compressed sensing briefly, current research and typical applications, and details the basics of compressed sensing theory.Secondly, in various reconstruction algorithm, we deeply studied several common convex relaxation algorithms, besides, we studied several novel nonmonotone line search methods, and on this basis making an improved nonmonotone Barzilai-Borwein gradient method. Through a large number of simulation experiments, we found that when they reach the same relative error, improved signal reconstruction algorithm requires less iterations, but the running time increased more than nonmonotone Barzilai-Borwein gradient method.Finally, for the problems of the above algorithm, we suppose a new nonmonotone Barzilai-Borwein gradient method. The algorithm takes advantage of the convergence characteristics of the new nonmonotone line search methods and searches for the optimal solution by the approximate functions of objective function, obtaining the value of iteration direction, then it uses a new method to obtain nonmonotone line search step. Simulation results show that the new nonmonotone Barzilai-Borwein gradient algorithm can not only reduce the running time of the algorithm, but also significantly reduce the iterations of the algorithm, thus speeding up the convergence rate and improving the reconstruction performance of the algorithm.