A Primal Dual Active Set with Continuation Algorithm for the \ell^0-Regularized Optimization Problem
We develop a primal dual active set with continuation algorithm for solving the \ell^0-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it first identifies the active set from both primal and dual variables, and then updates the primal variable by solving a (typically small) least-squares problem defined on the active set, from which the dual variable can be updated explicitly. Under certain conditions on the sensing matrix, i.e., mutual incoherence property or restricted isometry property, and the noise level, the finite step global convergence of the algorithm is established. Extensive numerical examples are presented to illustrate the efficiency and accuracy of the algorithm and the convergence analysis.
Code (0)
등록된 구현이 없습니다.
Tasks
compressed sensingSimilar Papers 제목 키워드 기반
A Unified Primal Dual Active Set Algorithm for Nonconvex Sparse Recovery
In this paper, we consider the problem of recovering a sparse signal based on penalized least squares formulations. We develop a novel algorithm of primal-dual active set type for a class of nonconvex sparsity-promoting …
Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs
We study the problem of computing an optimal policy of an infinite-horizon discounted constrained Markov decision process (constrained MDP). Despite the popularity of Lagrangian-based policy search methods used in practi…
Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs
We study the problem of computing deterministic optimal policies for constrained Markov decision processes (MDPs) with continuous state and action spaces, which are widely encountered in constrained dynamical systems. De…
continuous-controlContinuous ControlPolicy Gradient MethodsRobot NavigationPrimal-Dual Rates and Certificates
We propose an algorithm-independent framework to equip existing optimization methods with primal-dual certificates. Such certificates and corresponding rate of convergence guarantees are important for practitioners to di…
BIG-bench Machine LearningA Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance
We study reinforcement learning by combining recent advances in regularized linear programming formulations with the classical theory of stochastic approximation. Motivated by the challenge of designing algorithms that l…