Augmented Primal-Dual Algorithms On Sparse Recovery Models And Applications

Sparse recovery has so widely applications in the fields of image processing,cancer detecting,climate prediction,machine learning that lots of attentions and research results on this topic appeared recently.However,with the upgrade of data detecting and depth of research,demands of high accuracy as well as fast speed cannot be met by lots of current sparse recovery algorithms.This makes first-order primal dual algorithm play an increasingly important role because of its simple representation and fast speed.At the same time,more nondifferentiable sparse recovery problems emerged and urged the developments of primal-dual algorithm.This thesis mainly focuses on primal dual algorithms for classical sparse recovery problems and its extension.Its main work includes:1.A new algorithm is proposed for l₁-minimization,which combines the proximal point algorithm and primal-dual method under the Lagrange dual analysis.And then its accelerations are also presented on the basis of Nesterov accelerated scheme and restart/skip techniques.Compared with linearized Bregman algorithm,the new proposed algorithm can avoid to select model parameters,so that its application is beyond the compressed sensing problem.The last simulations verify the advantage of this new algorithm under the circumstance that parameter choice cannot meet the condition of exact recovery.2.Two new perspective to solve the block sparse recovery problem is presented,which extends the original one.The first is block-sparsity based linearized Bregman algorithm;The second is block primal dual algorithm based on proximal operators,which can avoid parameter adjustments in block-sparsity based linearized Bregman algorithm.Convergence analysis is given,and numerical results demonstrate speed and accuracy of these algorithms are both increased twice when compared with linearized Bregman algorithm.3.Augmented primal dual algorithm framework with continuation for solving a class of general norm minimizations has been proposed based on general augmented primaldual algorithm.It can be applied widely,and a lots of concrete recovery problems verify this framework can at least speed up to twice of the original one.