Sensing Matrix Constructions And Preconditioned Method For Compressed Sensing Problems With Gabor Frames

Compressed sensing has received extensive attention in the fields of signal pro-cessing,mathematics,statistics,and computer science in recent years.Sparse signal reconstruction in compressed sensing is a class of optimization problems.Primal-dual algorithm is a kind of second-order optimization methods since it utilizes the informa-tion of second-order derivative.Second-order methods have numerous advantages.But it has one drawback: it involves solving systems of linear equations.In this paper,we exploit circulant matrix to construct random sampling matrices whose matrix-vector product can be calculated by FFT.We also propose an inexpensive and efficient pre-conditioning technique for linear systems using second-order methods.The details are as follows:(1)We propose three kinds of sampling matrices which are based on circulant matrix to reduce the computational cost.It can be shown that these matrices obey sub-Gaussian distribution and thus satisfy the restricted isometry property.Hence,they can be used as sampling matrices for compressed sensing.Compared with common random matrices,these new sampling matrices can effectively reduce the computational cost of reconstructing the signal.We compare these three sampling matrices through numerical experiments,and analyze the characteristics and applicable scenarios.(2)The condition number of linear systems becomes very large when Newton it-eration reaches the optimal point.As a result,the convergence speed of CG method slows down.Preconditioning technique should be used to speed up the convergence.We provide an inexpensive and efficient preconditioner.Numerical results show that the CG's iteration steps are significantly reduced by utilizing preconditioning.Com-pared to existing preconditioning method,the preconditioner in this paper is easier to solve and takes less time.Finally,we compare the new algorithm with the commonly used TFOCS and Tw IST method in compressed sensing field.The numerical results show that the new approach is practical and efficient.