A Study On Gradient Descent Regularized Orthogonal Matching Pursuit

With the rapid development of information technology and the advent of the 5th gen-eration communication technology,tasks dealing with high dimensional data are emerging in signal processing more and more often.Due to the disaster of dimensionality,the enor-mity of the dimensions of data brings a lot of difficulties to researchers.However,many high dimensional data in practical fields exhibit some sparse characteristics,making the study of recovering useful information from sparse data a very important subject.Researchers found that only a small number of measurements are required to recov-ery sparse signals as long as the measurement matrix satisfies certain conditions.Given a measurement matirx and an observation vector,the problem of recovering the sparse signal generating the observation vector is called sparse recovery.Up to now,researchers have found many algorithms on this problem,including?₁relexation,Orthogonal Matching Pursuit?OMP?,Iterative Hard Thresholding and so on.These algorithms have their advan-tages and weaknesses in dealing with sparse recovery problem with different dimensions and sparsity levels.In this paper,we made a comparative study on existing iterative algorithms on this subject and summarized some of their common features,on the basis of which we proposed a novel algorithm called Gradient Regularized Orthogonal Mathcing Pursuit?GROMP?which performs well on high dimensional sparse recovery problems.We proved its convergence theoretically and provided a sufficient condition for GROMP recovering sparse signals exactly.We also proposed an efficient implementation of our algorithm.Finally,we verified by numerical experiments that our algorithm achieves the goal of exact recovery with a high probability when the signal is sparse.We also compared GROMP with OMP and ROMP and found that our algorithm beats OMP and ROMP when the dimension of signals is very high.