Theories And Algorithms Of Piecewise Sparse Recovery

Sparse Recovery(or sparse representation)is a widely studied issue in the field of signal processing,image processing,computer vision,machine learning and so on.Since signals such as videos and images,can be sparsely represented under some frames,thus sparse recovery can be successfully applied in a number of fields.Most of fast algorithms at present are based on solving l0 or l1 minimization problems and they are efficient in sparse recovery.However,the sufficient conditions on the sparsity and the smallest magnitude of nonzeros of the signal for l0(l1)minimization problems and algorithms are too strict.In another word,the sufficient con-ditions for successful sparse recovery are not well equipped.In applications,there are signals with structures,i.e.,the nonzero entries have some certain distribution.The researches on the structures of such signals also gain extensive attention in recent years.Previous researches mainly study the sampling matrix in union of orthogonal basis or block sparse recovery problem(nonzero entries appear in a few of blocks).Different from the study on block sparse recovery,we study the sparse vectors whose nonzero elements appear in an scattered way,i.e.,piecewise sparsity,and the corresponding matrix can be structured in a union of some bases(orthogonal bases is a special case).The key point of this thesis is to build a general framework of piecewise sparse recovery.We improve some feasible conditions on the sparsity and the smallest magnitudes of the signal based on the analysis of the piecewise sparsity and structured matrix.These conditions make it possible to enlarge the scope of successfully sparse recovery.Moreover,we propose several piecewise sparse recovery algorithms which can better preserve the smallest magnitudes of the signal.Thus piecewise sparsity enjoys both theoretical benefits and practical merits over general sparsity.Our main contributions are as follows:1.Theoretical results of piecewise sparse recovery.(1)We present the definition of piecewise sparsity of signals.By the piecewise structure,we obtain the improved feasible conditions for piecewise sparse recovery.The improved conditions also make a relation between general case and the unions of orthogonal matrices.(2)We give the improved performance guarantees of BPDN,OMP and Bregman ISS al-gorithms for piecewise sparse recovery.Thus,broaden the scope of theoretical guarantees on successful recovery.2.Piecewise sparse recovery algorithms.We propose three kinds of piecewise sparse recovery algorithms by using the piecewise structure of the signals.(1)Motivated by the algorithms of CoSaMP and OMMP,we propose piecewise OMP method(P_OMP)which aims at preserving the piecewise structure of signals.We show that P_OMP possesses the advantages of comparable approximation error decay as CoSaMP with more relaxed sufficient condition and better recovery success rate.Moreover,we propose an improved version of P_OMP:Threshold P_OMP(TP_OMP)algorithm which enjoys the merit of no prior information(such as piecewise sparsity of the signal)required.Numerical exper-iments on surface reconstruction by scattered data shows that TP_OMP are more suitable for piecewise sparse recovery than some general sparse recovery methods.(2)In consideration of the cases where large scale nonzeros are far lager than small scale ones,we propose the piecewise inverse scale space(P_ISS)method with deletion rule.Since P_ISS has similar framework with OMP algorithm,thus it runs fast in applications.Moreover,P_IS S converges to an l1 sparse solution.Numerical examples show that P_ISS are better at preserving the small scale entries than ISS method.(3)We propose a piecewise weighted convex optimization method equipped with Jacobi-proximal type ADMM,named as P_BPDN.We use multiple weight parameters to make a bal-ance among piecewise sparsity.We give the relations of weights under the framework of piece-wise sparse theoretical results.Numerical experiments applied to image decomposition show the P_BPDN is efficient for piecewise sparse recovery.In addition,we present a pseudo-heuristic regularization parameter selection rule(IRLS_dB)which solve the above type of convex prob-lem with adaptively parameter selection,the IRLS_dB algorithm performs better compared with some other selection rules.