Line Search Method For Solving The Compressed Sensing Problem

Compressed sensing（Compressed Sensing CS）has been widely used as a sampling theory.At much smaller than the Nyquist sampling rate,the sample signal is acquired by random sampling matrix,and then the sparse signal is reconstructed through a nonlinear optimized reconstruction algorithm.Compressed sensing is widely used in many fields such as information theory,image processing,wireless communication and so on.The compressed sensing signal reconstruction model can be expressed as a l₀ norm problem model.In order to reconstruct an image with high accuracy with less observation data,restricted isometric properties（RIP）are needed to design the observation matrix with incoherence.In this thesis,the sparse signal is reconstructed using a non-monotonic line search algorithm,mainly as follows:The first chapter introduces the research status of compressed sensing problems,KL（Kurdyka-Lojasiewicz）inequalities,line search algorithms and the preliminary knowledge related to the research.The second chapter introduces the equation constraint optimization model with the objective function of the compressed sensing problem.Because the l₀ norm problem cannot be solved directly,the l₀ norm is converted to solve the equation constraint optimization model where the objective function is the l₁ norm.Because the observation matrix is random,in order to solve easier,the signal reconstruction problem with noise can be expressed as an unconstrained optimization problem model with the compressed sensing problem.Under certain conditions,the objective function has the KL property.The third chapter discusses the convergence of the algorithm.We first give the iterative format of the solution,the form of BB（Barzilai-Borwein）step size and the non-monotone line search,then propose the specific calculation steps of the compressed sensing unconstrained optimization problem,and finally analyze the convergence of the algorithm when the objective function has the KL inequality property.The four chapter verifies the effectiveness and feasibility of the BB step non-monotonic line search algorithm by numerical experiments.We also compare it with other algorithms and verify that this algorithm can indeed get good results.