Research On Sparse Reconstruction Algorithms In Compressive Sensing

Compressive Sensing consists of compressive sampling and sparse reconstruction.Compre-ssive sampling acquires the dimension-reduced observation data by random projections andturns out to be a novel compressed sampling technology, which can be applied to real-timeacquisition and recovery of massive data, i.e., Magnetic Resonance Imaging, Ultra-WidebandSignal Processing and Astronomic Image Recovery. Sparse reconstruction exploits signal’ssparse feature thereby recovering the original high-dimension signal from the low dimensionalobservations. Sparse recovery algorithm is the active research area of compressive sensing.Large–scale sparse recovery algorithm mainly includes three classes: Matching pursuit,iterative hard thresholding and L1norm optimization methods. This paper expands the study,analysis and implementation of aforementioned three type methods.The major works in thispaper are listed as following:1)Proposing the algorithm named Compressive sensing matching pursuit(CSMP). It has theguarantee to recover s-sparse signal provided that3s order Restricted Isometry Constant(RIC)is less than0.23, which relaxes the RIC condition for recovering s sparse signal by matchingpursuit and improves the convergence speed. In order to adaptfor large scale sparse recovery,matrix-vector multiplication operator is equipped to select subsets of both random projectionmeasurements and sparse bases, therefore being able to utilize discrete cosine transform andwavelet transform and avoid explicit storage of large scale matrix.2)Proposing the algorithm named SCIHTBB(Sparsity constrained Iterative Hard thresholdingwith Barzilai–Borwein step size), which has Monotone and Non-Monotone versions.Convergence analysis are developed respectively based on asymmetrical restricted isometryproperty. To tackle the unknown sparsity problem, an adaptive sparsity framework is presentedutilizing secant method. Extensions are provided to handle group sparsity, non-negative sparsityand matrix completion.3) Design and analysis of the algorithm named FPSP3, which has three components includingfixed point iteration, the SPG2nonmonotone line search and warm start skill. The fixed pointiteration is derived from forward backward operator splitting and is decomposed into forwardgradient and backward proximal steps.The introduction of proximity operator indicates backwardproximal step reducing to soft-thresholding thrinkage. Convergent step-size condition is obtainedby proving the strong monotonicity of inverse of gradient operator. The use of nonmonotone linesearch SPG2significantly speed up the covergence of fixed point iteration. In sparse recoveryexperiment, the comparison with L1norm methods GPSR,SPARSA and SPGL1shows thatFPSP3has the advantages of speed and recovery accuracy.4) Proposing the algorithm named DADMM(Dual Alternate Direction Multiplier Method),which is obtained by applying ADMM(Alternate Direction Multiplier Method) to the dual formof primal sparse recovery problem. DADMM is a flexible framework for sparse penalty and hasthe capability to handle various lasso-style sparse penalty, including lasso, group lasso, sparse group lasso and overlapping group lasso. The convergence analysis of DADMM is developedbased on Douglas Rachford operator splitting technology.The experimental comparisions verifythe highly computational efficiency of DADMM.