Research On Reconstruction Algorithm Based On Quasi-Newton Gradient Pursuit In Compressed Sensing

The compressed sensing is a technique that combines the data acquisition and reconstruction by the sparse structures of the signal.As one tipical type of reconstruction algorithms,the greedy algorithms are widely used due to the fast iterative process,which calculate the estimated signal by solving the orthogonal projection problem using the least squares method.The accuracy is not high in solving the nonclassical linear problems by the least squares method,and in a single iteration,the orthogonal projection needs to calculate the inverse or generalized inverse of the matrix,which is resulting in a large amount of calculation.Therefore,on the theoretical base of the gradient pursuit idea replaces the traditional greedy iterative algorithm which calculate the matrix inverse or generalized inverse matrix,this paper focuses on the research about the quasi-Newton pursuit algorithms for the problem that the Newton pursuit algorithm introducing high-order derivatives,which has excellent reconstruction effect but high computational complexity.Firstly,the thesis briefly summarizes the theoretical framework and development of compressed sensing.Based on the research of existing gradient pursuit algorithms,for the problem that the high computational complexity of the quasi-Newton pursuit algorithm,called variable metric method based gradient pursuit(VMMGP),considering that the multi-step quasi-Newton method could constructs the approximate inverse matrix of the Hessian matrix,an improved algorithm called gradient pursuit algorithm based on multi-step quasi-Newton method(MSQN-GP)has been proposed.The algorithm directly approximates the inverse matrix of the Hessian matrix of the objective function by using multi-step gradient information,then updates the iterative direction,which avoiding the complex matrix inversion of the VMMGP algorithm and reducing the computational complexity.Secondly,from the perspective of reconstruction accuracy,the approximate matrix which caculated by variable scale method in VMMGP has some deviation compared with the Hessian matrix caculated by Newton method in theory,the deviation can be corrected by the disturbance term,which constructed with the function value and the gradient value through the modified quasi-Newton method.Therefore,the thesis proposes a futher improved algorithm based on VMMGP algorithm called gradient pursuit algorithm based on modified quasi-Newton method(MQN-GP).The algorithm uses the function value and gradient value to add the perturbation term to the single-step gradient difference in VMMGP,and corrects the approximation matrix deviation in the iteration,which improves the reconstruction accuracy of the algorithm.Thirdly,considering the reconstruction accuracy and computational complexity performance of the algorithm,based on MSQN-GP and MQN-GP algorithm,an improved multi-step quasi-Newton gradient pursuit algorithm(IMSQN-GP)has been presented.The perturbation term which consisted of the iterative function and the gradient value,has been added to the multi-step gradient difference of the MSQN-GP algorithm to achieve a more accurate approximation of the Hessian inverse matrix,then the iterative direction has been updated to realize data reconstruction.The algorithm avoids the calculation of the second derivative and the matrix inverse,reducing the computational complexity.Moreover,the addition of the disturbance term corrects the deviation between the approximate matrix and the Hessian inverse matrix,and improves the reconstruction accuracy of the algorithm.The thesis proves the descent and second-order convergence of the improved algorithm through theoretical derivation,and uses Matlab to simulate the existing gradient pursuit algorithms and improved algorithms.The simulation experiment mainly compares the performance of each algorithm from the perspective of reconstruction accuracy,computational complexity and storage requirements.It verifies that the improved algorithm effectively reduces the computational complexity on the basis of higher reconstruction accuracy.