Researches On Piecewise Non-negative Sparse Recovery Algorithms

Sparse recovery problem is widely used in many fields,such as numerical approximation,image processing etc.The Orthogonal Matching Pursuit(OMP)algorithm is a kind of greedy algorithm,which is very popular to be used for solving the sparse recovery problem.It has some advantages on running speed and convenience.This thesis combines the “piecewise sparsity”of the signals and the OMP algorithm,in order to improve the piecewise sparse recovery algorithms by enhancing the percentage of successful recovery for the random non-negative signals.The main works includes the following two parts.(1)We introduce the definition of piecewise sparsity of signals and a Piecewise Nonnegative Orthogonal Matching Pursuit(P?NNOMP)algorithm.In order to find a proper piecewise structure of the signals,the algorithm is used to test on the non-negative sparse signals with big difference between two pieces.Compared with the classic OMP algorithm,the P?NNOMP algorithm greatly improves the successful recovery percentage of the non-negative sparse signals and reduces the number of recovered wrong support locations for the piecewise sparse signals.Next,we try to use the pieceswise structure by the size(or scale)of the elements,and propose an Adaptive Piecewise Non-negative Orthogonal Matching Pursuit(Ad P?NNOMP)algorithm.This new algorithm divides the non-zero elements into two pieces according to their scales.By the Ad P?NNOMP algorithm,the number of wrong positions of the recovered non-zero elements are significantly reduced which shows the effectiveness of the adaptive piecewise algorithm.(2)In practical applications sometimes the sparsity of the signals can not be known in advance,so a Piecewise Stagewise Weak Non-negative OMP(P?SWNNOMP)algorithm is proposed.This algorithm is to improve the P?NNOMP algorithm.The P?SWNNOMP algorithm does not need to know the prior information of signal sparsity and can adaptively select atoms to the support according to the residual threshold,deleted component threshold and “weak selection parameter”.Furthermore,an Adaptive Piecewise Stagewise Non-negative OMP(Ad P?SWNNOMP)algorithm is proposed,combined with the piecewise strategy by the scales of the elements.We test different measurement matrices and signal types by comparing with the SWOMP algorithm,and it is found that the Ad P?SWNNOMP algorithm has better successful recovery percentage.It shows when the sparsity of signal is unknown,the Ad P?SWNNOMP algorithm can recover the original signals effectively by chosing some proper parameters.Some numerical results show that both the Ad P?NNOMP and Ad P?SWNNOMP algorithms have advantages on successful recovery percentage for random non-negative signals,compared with the OMP and SWOMP algorithms which do not consider and use the piecewise structure of signals.The numerical results also verify the feasibility and effectiveness of the piecewise strategy by the scales of the elements,and provide the necessary support by numerical experiments for the researches on the piecewise sparse recovery algorithms.